I would suggest the Class 6 SDHC card. You will see an improvement over the Class 4.
Besides, the only thing that uses a CF card out of my pretty large inventory of electronics is the Axim. In other words, the CF card is getting old...
As of a GPS. You would only need a GPS receiver, NOT a integrated GPS.
There are various ways of connection a GPS to an Axim. If you buy the SDHC card, that leaves you with a CF card slot free.
You can go with a CF GPS or better yet, a Bluetooth GPS. IMHO, the CF GPS has a worse signal than a Bluetooth. But then again, a Bluetooth GPS is a separate "device" you have to carry around or leave in your car.
I have a few suggestions for both types of GPSes
Bluetooth:
Garmin's GPS 10 (I am currently using it, it is absolutely awesome). My review
here and the official site
here
A less expensive option (about half the price of GPS 10) is the Garmin's GPS 10
x.
Here's the official site.
You can download Garmin's Garmin Mobile XT as a voice-guidance software for free. Remember to buy the maps!
As for CF GPS:
I have in my "arsenal,"
GlobatSAT's BC-337. You would need
iGuidance to use it as a voice-guidance software though. (I'm too cheap to buy it

)
Ambicom's CF GPS looks pretty cool too:
Ambicom