I tow a Honda Fit, manual transmission. EPA doesn't say 35-40, but I've averaged 36 MPG over 20K miles of mixed driving and get 39+ on road trips if I don't run A/C (A/C for summer driving costs about 2-3 mpg on a car that uses so little power to move it). Manual transmission Fit is variable on MPG because it has just enough power to be tempted to treat it as a tiny sport sedan, but does really well if you avoid that temptation and shift as early as possible.
SIL puts two bikes in his Fit with both rear seats down, one bike with one seat down, one passenger in the back. Removes the front wheels to do it.
I would look also at manual transmission Matrix/Vibe, but don't know how the seats work. Version with the smaller engine does almost as well as a Versa or Fit on MPG. I also looked at HHR, but although it had lots of space, the space wasn't as useful, more length than height. For lots of cargo room in this category, consider looking for a Honda Element. Honda won't say it is towable, but it is, and MPG of last ones made is not in the 35-40 range.