@SpudsMcToole
I can vouch for everyone who has suggested ruling out the TV as the issue. I only started out with the RPi/Retropie about 6 months ago. I started off using my LG 42" Plasma screen (bought in 2006) 720p. I definitely noticed lag like you describe (Mario slightly late jumping, etc.). It was a little disappointing, but I started reading and sure enough saw the suggestions similar to those above. My TV does not have a game mode.
Took my RPi to my brother's Samsung 50" TV and saw immediate improvement (even without game mode turned on). I can't be sure game mode helped in addition but I assume it was probably slightly better. Regardless, the TV made all the difference and it plays very well on his TV.
Now, I have the RPi connected to a 24" Samsung PC monitor that also works very well. In fact, nearly every TV/monitor I've tried was better than my TV.
In addition to the other suggestions above, I definitely agree you should try a couple different screens if you have access.
I'm also curious (now that I better understand the system) whether setting my RPi to 720p as default would've helped in the lag department.