Toutes mes recherches ont finalement abouti à la conclusion que si EF en général est mauvais pour les performances, MySql + EF est carrément de mauvaise qualité. Le choix de SO de L2S sur EF est une bonne décision et si j'avais eu accès à une base de données MS Sql au lieu de MySQL, j'aurais également évolué dans cette direction.
Malheureusement, je suis bloqué avec MySql car c'est gratuit et cela m'a obligé à abandonner EF. Je suis maintenant de retour au codage en dur de mes requêtes SQL à l'ancienne, testée et efficace, et les résultats sont bons.
J'ai donné un laissez-passer à MYSql + EF, mais j'aimerais entendre des gens qui l'ont utilisé avec succès dans un projet non trivial.