Yandex market capitalisation is over 4 billion US.
Not sure why size is a problem, I'd say use Google, they are practically perfect as an email provider.
Most of the small providers use free software webmail, mostly Roundcube. It'll be less secure and less reliable than google's, and they'll charge for the service.