I remember a college friend of mine playing games on his "smartphone" while sitting on the toilet in 2002. (The iPhone came out in 2007.)
His phone ran Windows CE, and I think it even had a browser on it. I even remember going out to look at "smartphones" in 2003, and later in 2005, and just being generally disappointed. The one that I looked at in 2003 was too expensive and clunky, (I was a college student on a budget,) and the one that I looked at in 2005 was too hard to figure out how to use. (Windows CE).
Ballmer's criticism of the first iPhone was that Microsoft had been shipping almost the same thing on phones with Windows CE for quite a few years. The big difference was the UI: The iPhone was a touchscreen and easy to figure out; Windows CE was difficult to figure out and used a stylus.