LaVerendrye is a good option, you still will have to pay fee's but it's about the closest big park to Albany.
Fishing can be great, but permits are pricey, I just buy a 3 day license and have it go into effect when I get a few days into the trip.
Bears are seldom a problem, a native told me once that bears eat moose calfs so bears get shot at by natives....just repeating what he said, no opinion one way or the other, but every bear I ever saw in LaVerendrye (and I've seen a few) made a mad dash for parts unknown.
Rivers Noire and Colounge are free, but only if you use a shuttle, well, thats what my outfitter told me, but you mentioned smallish lake routes.
Another option is ZEC Kipawa, smaller lakes, fees are reasonable and very little traffic compared to Algonquin which is close by. Fishing is also good but pricey.
Do you have Hap Wilsons "Rivers of the Ottawa Valley"? Lots of info there and good info for a lake to lake paddler.
Just google it, nice information site and I can give you some added tidbits (like you need to pay cash, no plastic)