codice:
public static List<COMUNI> GetLista (string iniziale)
        {
            using (var entities = new AgriEntities())
            {
                var lista =
                    ( from ist in entities.COMUNI
                      orderby ist.Nome
                      select ist ).ToList();

                return lista.Where(c => c.Nome.Substring(0,1).Equals(iniziale));
            }
        }
In questo modo la where la fai fare a linq to object e non a EF.
Se cosi funge (non ho fatto esperimenti) allora il problema è come EF traduce la query verso il database che non è sempre ciò che noi ci aspettiamo.
A questo punto tocca a te decidere se lasciare le cose cosi (magari l'intera lista non è poi cosi grande) oppure trovare un workaround per forzare EF a fare la query giusta.