The original iPhone App Store launched with 400 apps, but the hardware was out for a year by that point.
That being said I don't know what the first "wow" app was for the iPhone other than games?
It was that beautiful touch screen + real apps, namely email and a browser. Before that, the number of devices with an email client not controlled by BlackBerry and a full on browser was very small.