Well, the iTunes store came online in 2003. Not much of a stretch to foresee a marketplace for apps much like the marketplace for music. Whether it would be successful or not is another thing.
I disagree; apps were never a guarantee. Steve was adamant about not having 3rd party apps on the iPhone for a long time. However, with 20/20 hindsight it's easy to see.
Steve was also adamant about not doing a phone in the first place, not doing a tablet, etc. The point being that Steve always publicly denied wanting to do something that privately he was already investing significant resources in doing.
