The New Forest is one of my cycling haunts as I live in Winchester. I'd say yes, go for it as the Forest is probably one of the most cycle-friendly bits of countryside in the south of England.
Hire - There are plenty cycle hire companies. I can think of two straight away in Brockenhurt (next to the station) and Burley. Brockenhurst would be a good base as its pretty and you've got fast rail links to the coast (Bournmouth) and London.
Riding. Aside from the A31 and A35, there's a blanket 40mph speed limit on all the roads. This isn't always followed and locals are usually the worst offenders, but it makes it feel a little less pressured. High summer at weekends can get very busy with traffic, particularly around the towns, so try to plan for cycling during the week for quieter roads. The terrain is gently rolling nearly everywhere, so anyone of reasonable fitness will find it a doddle. The only really hilly bits I can think of are around the western border of the Forest towards Fordingbridge.
Routes - If you avoid the few A roads that pass through the forest, then any route you choose will be fine for cycling. I'd recommend the Bolderwood and Rhilefield Ornamental Drives noth of Brockenhurst for a ride. They are beautiful and very cycle friendly. The only thing to watch out for is that minor roads joining the A31 do actually allow you to cross. I can think of one or two that just end in a junction and the A31 armco effectively stops you from crossing. Look carefully at the map for an underpass or bridge.
I'd better get back to work now. I'm sure there's others on here with more......