La forme la moins formelle est Cordialement. Je la trouve affreusement sèche mais dois reconnaître qu'elle est acceptée. Elle peut d'ailleurs être améliorée par bien cordialement, voire bien à vous, ou quelque chose du même ordre et déjà expliqué ici. Cette forme s'utilise beaucoup pour signer des e-mails professionnels ou commerciaux, l'e-mail étant par nature moins formel qu'une lettre. J'ai déjà rencontré cette forme par écrit, mais j'ai trouvé cela peu avisé de la part de l'auteur.
Ensuite vient Avec mes sincères salutations. Ceci est tout à fait approprié pour une lettre qui se veut polie mais sans formalisme excessif. C'est également approprié pour signer un e-mail, et c'est même plutôt agréable à lire. Un intermédiaire entre cette forme et la précédente est Sincères salutations.
Enfin, vient le fameux Veuillez agréer, [titre], l'expression …...
de mesmes sincères salutations, ou encore
de mesmes salutations distinguées
del'expression de mes sentiments les meilleurs/les plus sincères (attention à celui-ci ! Il s'adresse à une personne du même sexe uniquement afin d'éviter toute ambiguïté !)
del'expression de mon profond respect (cette forme est militaire), ou encore
de mesmes salutations respectueuses (c'est personnel, mais c'est cette dernière qui trouve ma préférence).
The least formal is Cordialement. I find it awfully plain, but I must admit that it is accepted. It can be refined as bien cordialement, or bien à vous, or similar. It is often used to sign professional or commercial e-mails, which are in nature less formal than a letter. I came upon paper occurrences of this valediction, but I consider them ill-advised.
Next comes Avec mes sincères salutations, which is perfectly appropriate for a polite letter that tries to avoid excessive formalism. It is also appropriate to sign e-mails, and reads rather pleasantly. A shortened intermediate form is Sincères salutations.
Then the classic: Veuillez agréer, [titre], l'expression …...
- de mesmes sincères salutations,
- de mesmes salutations distinguées,
- del'expression de mes sentiments les meilleurs/les plus sincères (be careful with this one! it is addressed only to a person of the same sex to avoid any ambiguity!)
- del'expression de mon profond respect (military form)
- de mesmes salutations respectueuses (this one has my preference).