Whether you have a contract with the mobile phonw will make a massive difference to the price.
I use a T-Mobile MDA compact (which is a rebadged imate Jam) The phone was free on my contract, and is a windows based PDA/Phone, but slightly smaller than a standard PDA, and fits in my top pocket nicely.
I have added tomtom mobile to this (£200) which works like an absolute dream.
I could have had the co-pilot software much cheaper, but the ease of use, popularity of tomtom(and thus more add-ons available ie voices, speed cameras etc) made the tomtom the right option for me.
The phone has bluetooth but not wi-fi. I believe 'this years' model (MDA Vario) also has wi-fi which would be handy for VOIP calls.
There are quite a few smartphones on the market now, some running windows, some running a version of symbian (i think the Nokia's are symbian based)
I have also added a car charger for the phone (£6 on ebay) and a small holder for the dashboard (£10 Halfords)
If you are looking to buy the phone outright (PAYG or SIM Free) I think you will be looking in the region of £150-£200.