Hasn't anyone played Pitfall for Atari 2600? Although the screen didn't scroll as in SMB, it was the same concept, made far earlier. You spent time running, jumping, etc. Pitfall 2 expanded on this with a game surprisingly large for an atari.

Also, i think SimAnt was one of the big precursors of the Starcraft/Warcraft/TA games. It is very primitive, but the gather resources-lead an army-build a base theme was defined there for the first time I'd seen it. There were even different unit types = workers, soldiers, etc... The main limit was you could control only one ant at a time.

And you cant forget civilization 1... I think the oldest game i still play on a regular basis.