As usual, the CPF people come through.
Like Sub said, make sure to go to a local bike shop.
Make sure you both get the proper fit: a bike shop will assure this.
You must have the right size frame!
You can always adjust the saddle, bars, etc, but the frame is static.
Once you have a good overall fit, everything else will fall into place.
Trek and Giant both have great bikes for your needs.
I worked at a bike shop which sold both) a few summers ago.
We sold a lot of Trek 7000 (hybrids), 3000 and 4000 (mountain) series to people like yourself.
We also sold a lot of Giant Sedonas, Cypress (hybrids), Rincons and Boulders (mountain).
Hybrids or comfort bikes usually have larger wheels, narrower tires, and a much more upright position. They are very nice around-town bikes. The larger wheels allow you to roll-over stuff easily.
The downer is that they tend to be pretty heavy, partly due to low-end suspension forks and suspension seatposts. They are still GREAT bikes, though.
The "lower-level" mountainbikes are also very comfortable, but are more off-road worthy.
I generally recommend them because of the flexibility (on road or off), and the wheels, which allow you to put some really fat tires on.
Big, fat low-pressure tires make for a very smooth ride, and won't kill you if you end up on a gravelly or sandy road.
Generally, the "mountainbike" has less proprietary parts as well, but certainly isn't always the case. You can often find deeply discounted parts online, due to their standardized nature.
Also, the mountainbikes are upgradeable to be more off-road worthy. Even a $300 bike with some new tires can be a load of fun off-road.
*If you can, get a bike with a 1 1/8" head tube. This will allow a lot of flexibility for a future fork upgrade...if needed.*
For $300-$500/bike, you both will have great bikes that will last a very long time.
Bob