That's going to be a tough one to call. Nokia Communicator had diary (calendar), web browsing and email features in the 90s. You could also tether off it, but it was dialup and most phones could do that.
That was pretty much the definition of a smart phone at the time.
It may depend on your culture, but Blackberry and Windows Mobile phones were both fairly common in business circles years before iPhones.
The iPhone was an incremental advancement, not a major invention out of nowhere. The first iPhone was actually pretty crap compared to some models on the market. It wasn't until the 3G model that iPhones took off.