Dream Mail - $50 - Six Island PokeMart
Retro Mail - $50 - Celadon Department Store
Surprisingly, these are the only two mail types that can be bought in Firered (according to Bulbapedia)
Even though your question specified buying mail, you can also find the Fab Mail by trading for the Jynx in Cerulean City.