I'm going to tentatively say Rayman or Pokemon Yellow, but I could be wrong on both accounts. I played Fallout, Total Annihilation and Grandia quite early too, but if it was before I started getting consoles I have no idea. I used to play Blade Runner too at a similar time.
I had Bugs Bunny Lost in Time, I'm glad to see it being mentioned it was a great game!