We settled on a 2003 Matrix. I know the question was asked about the Fit vs the Versa, but somebody else chimed in about the matrix so I wanted to give it my vote as well. When looking at the vehicles in this category, I found that the older Matrix has more cargo space than the new one, but the newer Fit has more room than the old style.
I test fit 56 P3C, and it can fit on its side without taking the front wheel off, or I can take the front wheel off and stand it up and secure it along the pasenger side side leaving the bulk of the cargo space for another bike or gear, etc… However, I have to drop my seat to get it to fit due to the rear bottle holder.
We have also fit my 29’er in there on its side with the front wheel removed on several occasions.
If you decide to look at the Matrix, the Pontiac Vibe is the same car. Its made by Toyota for Pontiac and they are usually a bit less.