For some reason I doubt you ever tried to use a pre-iPhone mobile web browser (Maemo excluded of course, but then, the 770 wasn't something the average consumer would pick up. The N800 wasn't particularly mainstream either).

Then there's the whole optimize the UI for finger touch. Imagine being able to efficiently and easily navigate the UI with one hand without having to sacrifice a huge, high resolution (relatively, for the time) screen. For some reason, nobody else could figure that out. PalmOS and WinMo hadn't actually changed in years and were stuck with stylus-oriented UI's. Some WinMo phones didn't even have that. Symbian was stuck on tiny screens with button-only interaction. One handed and somewhat easy, but lacking efficiency and unable to display much data at once.

The media player, though, wasn't particularly innovative. Just a logical evolution to a finger-touch UI.

Visual Voicemail was also a brilliant idea.

That said, the iPhone should have flopped because all it's benefits (with the exception of Visual voicemail, and maybe the finger-touch UI) had/have severe flaws, not to mention the dozens of other shortcomings. The two reasons I believe it succeeded:
1. It's Apple. Kinda similar to how people got hooked on Windows in the early 90s.
2. The competition was even worse. An analogy: iPhone OS 1.0 was a 4 tool Swiss army knife missing two tools and the front half of the blade completely flat. The competition was a 1 foot (~.3 m) wide monster with dozens of tools.