My general advice is to avoid eating beef in France, particularly if you're from the US. The cuts here tend to be tough, gristly, and unevenly cooked. One exception is the competing steak/frites places that are amazingly good in their simple formula. The other exception are the various Aveyron restaurants you see advertising beef from the Aubrac. The meat is still pretty chewy, but the flavour is great.
We had a very nice lunch yesterday at the Maison de l'Aubrac. It's just a stone's throw from the Champs Elysee, but don't let that worry you. It's a good casual place, set up like a rustic country inn but with proper service and a menu that is all beef, all the time. The best dish I had was asparagus with beef cheeks, beautifully tender and flavourful without the creepy gelatinous fat you often get with joues. Nice steak tartare, too, and while my faux-filet was not terribly good Ken was impressed with his brochette of veal.
And as bizarre as it sounds they advertise being open 24 hours a day. So if it's 4AM and you need some raw ground meat, here's your place.