Had the Vx for almost two years, did great and I loved it! Started to get a little squirrely (crashing alot) which gave me a good excuse for a M505...
Color rocks! Totally unecessary, but fun to have. IMHO, the M500 is bare minimum to me and an improvement over the Vx: better screen, more durable writing/graffiti area, memory card expansion, faster OS.
OTOH, just about ANY Palm will make your life better... if money is an issue, I'd go for the Palm model that can run OS 4.0 or better... second, I'd look for rechargeable batteries, then a memory card expansion, in that order.
Can't comment on Win CE models, other than it's cool to not have to rely on Microsoft for support! [:P]
Have fun!
Edited to add: Stay away from the VIIx! The wireless models are way underdeveloped, will cost LOTS in monthly service fees for gimmick level performance, and are TOO BIG! The joy of the Palms is having them immediately available- in your shirt pocket is ideal. That way they get used, rather than end up holding paper down on your desk. Form factor is almost everything and smaller is better, always.