When picking out a font, always go for readability over style. That doesn't mean you can't pick stylish fonts. But be sure to look at the anime's "main" color scheme, how "busy" it looks, and so on. The busier it looks, the bigger/easier you want the font to be. You might even use an ugly solid color. If it's not too busy, look at the show's color scheme. Pick out a few colors that are prominent, and look at a color wheel to pick out different, "matching" colors for the font.

Accented analogic color schemes can work very nicely. So can plain old triads. Plug the anime's "main" colors into:
http://colorschemedesigner.com/
and play around.