Lets say for argument's sake you want to do 5mph on some of the really steep bits, and for the sake of this we'll ignore the power required and just look at the pedal revs in different gears. The rpm's shown are approximate and dependant on the actual diameter of the tire you're using and how worn it is but for a comparisons this'll work. I'm guestimating a 700x23ish tire.
So your 5mph will take.
30x25 = 54rpm
30x27 = 58rpm
30x30 = 64rpm
With most Shimano rear deuraillers you can get a 30 sprocket on there.
Harris Cyclery Century Special 13-30 9-speed Cassette - harriscyclery.net
It's not the lightest cassette but you'll not notice the slight extra weight when on the hills.
With that swap you'll just need a new cassette, if your chain is fairly new and in good condition. It's it's a year or so old and your ride regularly, get it changed too.
If you wanted any lower, you'd need a long cage rear mech - like an XT, XTR or LX (with a barrel adjuster) and a new chain in addition to the new cassette. The shimano mountain bike rear mechs will work with the road bike STI brake lever/shifters, whether you have 8, 9 or 10 speeds.
At 5mph with the lower gears:
30x32 = 69 rpm
30x34 = 73 rpm