Are we talking smartphones as in PDA-phones as well? The idea of a PDA-phone is that it rolls a PDA with phone capability, along with a touch screen and internet access and the ability to install 3rd party apps.
My 1st PDA-phone was the Sony-Ericsson P910i in June 2005. It had the Orange app store and I remember buying Worms (PC game) for it for £5 and it played pretty well. The downside is that the game was tied to the handset, so I couldn't carry it over to my next phone.
If we're talking strictly Android, iOS or Windows, then it was my Samsung Galaxy Apollo (Orange's name for the Samsung Galaxy 3) in June 2010.