Only end-to-end encryption as pepe suggests can offer something significant - and still won't save you in cases like voice messages etc.
Also 'rooting/jailbreaking' the phone or not may be an important question if concerned about illegal client-side software installations. Rooting the phone can lead to opening it up to exploitation if not careful (it sometimes leaves the ssh daemon open with default password) - but then again you may be able to install security software only after rooting it. The recent iPhone/iPad exploit demonstrates this: it takes advantage of a fault in a font parsing routing in the iPhone software while opening a carefully constructed PDF file, and uses this fault to get root access. The thing is that after exploitation, you can apply a patch for the fault so that no one can exploit your device without your knowledge if you happen to open a malicious PDF. Without jailbreaking the device you can't install the patch (it's not official yet).
Phone operators (or secret agencies) have the authority and means to push and install software on your device without your knowledge. But it's not only them, look here and here for example. Pushing software and firmware updates can be done to any phone - no need for it to be 'simple' or 'not smartphone'.
Another interesting factoid: The chat logs between Bradley Manning and Adrian Lamo that Wired recently released contain multiple references to phone tapping by secret agencies, for example that it took NSA 50 people and 6 months to figure out how to tap the iPhone. The most interesting part is that wiretapping is something commonly done and they don't have to get a warrant or think about privacy rights while doing it because they do not present the wiretapping data as evidence in court to be challenged - they only use the data to obtain leads to other evidence.