What qualities should I be looking for when making the best French Toast?
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.