Sounds like you need to get an ASN and run BGP with your ISPs. This is not difficult and does not require "big iron" for routers if you just accept a default route from each (and redistribute it into your routing protocol). See the white paper on multihoming on my web site for some other alternatives and a general discussion. See Chapter 8 of my book High Availability Networking with Cisco for a more detailed discussion (and example configurations, none of which exactly match your configuration). See Halabi's book Internet Routing Architectures for everything you could possibly want to know about BGP :-).
I have implemented this for several clients, and the most time consuming part is usually filling out the paper work to get the Autonomous System number assigned, followed by babysitting the routers while each ISP turns up BGP for you. If done properly, no down time is required. The only potential sticking point is if you are currently using a public address range smaller than a class C which cannot be expanded to at least a full class C (/24 prefix) that both ISPs are willing to advertise to the rest of the world.
Good luck and have fun!
Vincent C Jones
www.networkingunlimited.com
