Changing the permalink structure back won’t reduce your CPU usage that much. That stuff happens on the Apache side of things (using mod_rewrite), and it’s pretty fast. It might help a bit, but it’s a HUGE pain if you have nice, readable, search-engine friendly URLs at the moment.
One of the best ways to reduce CPU usage is to implement caching. If you’re getting WordPress to serve static content instead of having the content fetched from the DB and processed every time, you’re saving a lot of resources. The two most popular caching plugins are http://wordpress.org/extend/plugins/wp-super-cache/ and http://wordpress.org/extend/plugins/w3-total-cache/ right now. I personally use WP Super Cache, but there are good reasons to look at W3 Total Cache. Depending on the setup, one might end up being a lot better than the other for you.
EDIT:
I looked at your site as well… It’s being served very slowly from your host. This might be because of a lot of plugins, or some less-then-optimal custom code — but I think it might also be a good idea to look at what other hosting providers could offer you. I use MediaTemple and I love them. However, I also only host one WordPress site per shared hosting instance, and pass the hosting costs on to my clients. I find this to be a better option for something like WordPress which is pretty resource intensive on a site with even moderate traffic.