GPS bluetooth receivers are quite cheap on
ebay aswell. But you might need to be happy pairing them up to phones etc to get it to work.
Not sure about the phones you mention, but my X1 was windows mobile, crap as a phone interface at the moment (until mobile 7 gets released) but is ok as a PDA operating system, there seems to be a few apps out there for this platform, but have just really started to look into different options/apps.
I beleive iPhone has several app's available - i think has built in gps aswell but no idea how it performs - someone else here might know.
The other phone platform is Google's Android, but again you'd have to research what is available
A lot of phone's have a specific OS to that phone or range of phone's, eg my Sony k800 i s very limited for addon's.
the more generic the OS - windows mobile - iphone - android etc the more choice of software you get