I would definitely recommend getting a "Pocket PC" powered PDA rather than a a "Palm OS" one - it's a much more powerful operating system and much more like normal Microsoft Windows. I also have an iPaq 1910 and find it a great little machine - unfortunately it's no longer on sale, but you can still get hold of the 1940 which has Bluetooth as well. Most modern PDAs will allow you to add a memory card and I recommend this as you can then keep all your extra programs and data on it and leave the main memory for the system and built in programs.

There's some great software available very cheaply or even free - I've got a great Midi File player. I also have TomTom Citymaps and RoutePlanner which when I connect my GPS will show where I am anywhere in the country. I also keep the lyrics of all my songs on my PDA (in Pocket Word format}) - just in case I need to check up !

Finally, as my mobile phone has a modem, I can connect to it via Infra Red and even go on the net and post to Mudcat !