I wouldn't be too concerned about the CR-V's middling score in the small overlap test. This is a new test, and any of these tests covers one possible crash scenario (in this case head-on with a small overlap, most likely on rural two-lane roads) out of a very large number. The CR-V scores well in the other tests.
Both Mazdas (did you mean CX-5?) also score well in the safety tests.
The hatchbacks will get significantly better gas mileage than the crossovers, can't beat physics.
To get good fuel economy in the Mazda3, you'd have to get one with a SKYACTIV engine, which was introduced in the 2012s (and not all 2012s).
I'm personally not a fan of how the CR-V looks or drives, but these things are subjective. If you like it, that's what counts.
The Mazdas are more fun to drive than the Hondas. The main negatives on the 2004-2013 Mazda3 are styling, somewhat cheap interior materials, marginal fuel economy (w/o SKYACTIV), higher than average noise levels (which Hondas also suffer from), and a tendency to rust where the roads are salted (not an issue in Virginia, but watch out for cars that spent some time in the north).
A lot of people like the Honda Fit for its combination of roominess and fuel economy, but it did score a poor in that new test. Worth considering if the car won't often be driven on two-lane roads at fairly high speeds.
The 2009-2012 Elantra Touring didn't sell in large numbers, and tends to be very reasonably priced as a used car. The SE trim is especially nice. This car wasn't related to the Elantra sedan. Instead, it was a car designed primarily for the European market, where it was marketed as the i30 "estate" (British for station wagon). As such, it's has quite a bit more rear seat and cargo room than hatchbacks like the Mazda3--and nearly as much as the CR-V. But it drives like a hatchback, not a crossover. Fuel economy is just okay. It wasn't crash tested in the U.S. In the European NCAP tests it scored okay but not great--better than the European Civic of the same years.
Here's a specs comparison with the CR-V:
http://www.truedelta.com/Hyundai-Elantra-Touring/specs-876-2012/vs-CR-V-110-2012&body_1=18&pt_1=1281&body_2=14&pt_2=141
The Subaru Forester also has a lot of fans. But avoid the 2011, as it's prone to engine problems. And all Subarus have a tendency to get expensive to maintain after 100,000 miles.
Final tip: if your wife really wants one car, and you get her another one, you'll never hear the end of it until the car is gone :)