Changing Multiple WordPress Page URLs/Structures Safely (No 404)

Right now, we have a multiple location business website that we are working on redesigning and beefing up the SEO. After doing research we would like to change the structure of MANY pages within the website. Right now, our site’s links run as this:

http://clearchoicephotobooth.com/contact-us/cleveland-office
http://clearchoicephotobooth.com/pricing/cleveland
(And so on for several cities and many pages.)

We would like to change them to the following:

http://clearchoicephotobooth.com/cleveland/contact
http://clearchoicephotobooth.com/cleveland/pricing

What is the best way to do this, as not to create 404 pages for those that have bookmarked links or links featured on our blog, etc.

Any help would be appreciated! Thanks!!