Why wouldn't "Wir würden einen Auto mieten" work in lieu of "Wir würden einen Wagen mieten."
Der Wagen und das Auto haben verschiedene grammatikalische Geschlechter. Der Wagen and das Auto have different grammatical gender.
Leihen?
leihen is "borrow" and does not involve an exchange of money, whereas mieten (rent, hire) does.