Je vous prie d'agréer, Madame (Monsieur), mes salutations les meilleures.
This part of a letter written in French is tricky. In the olden days, distinctions were made to whom you are addressing your letter: the clergy, your member of parliament, a professor, a medical doctor, a lawyer, etc. As well, distinctions were made whether you wrote to a woman (veuillez agréer, Madame, l'expression des mes sentiments les meilleurs) or a man, in which case you would not use "sentiments" if you, the writer, were a woman. This is just what I can say about the subject in a nut shell, as it is so vast, a whole book could be written about it.
These days, all these differences do not fall into play any longer. However, you still have a certain choice of:
Recevez, Madame (Monsieur), mes salutations les meilleures.
Veuillez agréer, Madame (Monsieur), mes salutations les meilleures.
One important point, however, is the mention of "Madame", if you are writting to a woman, and, of course, "Monsieur", if you are writing to a man.
These are the rules valid in Canadian French. I have two Manual published in France in front of me, and it seems that formulas such as:
-- Je vous prie de croire, Monsieur, en mes sentiments distinués
-- Je vous prie d'agréer, Monsieur, en mes salutations distinguées
-- Recevez je vous prie, Monsieur le Sénateur, l'assurance de ma haute considération
are still in use.
One last point, if the person has a title, you must repeat the title (e.g. Monsieur le Directeur) in your salutation.
I hope I have covered the subject in a satisfactory manner. As I said before, a whole book could be written about it.