Like many others, Sonic 1, on the Master System. My mum bought me the console for christmas... she had a go first though, and couldn't figure out how to jump, even though there were only 2 buttons, both of which were jump.
I think the next game I played was actually a movie tie-in verison of Terminator 2. It wasn't utterly terrible either, by movie game standards.