Tu as les classiques
-Kimsufi(prestataire OVH)
-Dedibox(prestataire Online)
-OneProvider
Tout dépend ton utilisation, l'espace disque dont tu as besoin, la connexion Internet notamment... Pour ma part j'ai essayé Kimsufi et Dedibox(les offres les moins cher) et j'étais satisfait des deux serveur.
Pour ce qui est de la distribution cela dépend du script, certain sont compatible avec une distrib particulière et certain script sont compatible sur tout ou presque

Mais je te conseillerais Debian 7/8 ou alors Ubuntu 14/16
Pour l'encodage je n'y connais pas grand chose ^^ dsl