Should it be a thick slice of bread? Should it be made with challah bread? Should it be slightly crispy and brown on the outside but mushy on the inside?
Great french toast starts with the bread. You're looking for two things: thick slices, and staleness. Why stale? Stale bread has enough firmness to stand up to the custard. If you don't have stale bread available, you can set it out the night before in a simple wire rack. At least 8 hours should be enough to stale it up nicely. They will be rather firm to the touch.
The ideal finished product is crispy on the outside and creamy in the middle. This might be what you mean by mushy, but mushy in my mind is kind of negative. The key to accomplishing this is to let your bread soak in the custard only 30 seconds per side, but then move it to a rack to sit for another 2 minutes further. This extra set time allows the custard to penetrate deep inside the bread, and be distributed much more evenly.
The final trick to getting a nice crispy crust, is to cook it twice. First in the pan/griddle as you normally would, but then 5 minutes in a 375 F oven on a rack. This brief oven stint crisps up the exterior nicely.
I highly suggest watching Alton Brown's Good Eats: French Toast episode. That's where I learned the oven trick, and his recipe hasn't done me wrong since.
Regarding challah, I've never had it, but based on the Wikipedia description it sure sounds like a good candidate. Just make sure you slice and stale it overnight.
Challah is indeed wonderful for French Toast, as is brioche. The breads are already rich with eggs so that gives them a head start.
A style that I learned about from Molly Wizenberg's book, A Homemade Life, is to cook it the toast in rather more oil than you would normally expect to use. This results in a crispy, almost fried crust and a creamy interior that I think is delicious.