Do you have the 2.0 software on it even (with the app store)? If you have the app store you can download apps from that. If you are still on the first generation of software, before the app store, it gets a little trickier as the latest firmware update from Apple can not be unlocked, at least if you have a normal 3G phone. Not sure if it is different for the first gen phones.
Edit: It looks like if you have a first gen iPhone you can upgrade to the latest firmware without any worries in iTunes then run QuickPwn from the iPhone Dev Team (free software you install on your computer) and your phone will be re-jailbroken and unlocked.