Reincarnation does the following. You basically choose to reincarnate when you really want to do one of these. When you do it then becomes when it is most appropriate for each.
- It improves your stats. The effect is far more pronounced when you do it at higher levels, especially after more reincarnations. This also leads to more points to spend on the bonus stats.
- It gives you a chance to reassign your bonus stats. Eventually you'll reach the point where everyone will have at least 10 points and fancy desks... except maybe that one loser Blue Skull who you don't like and only created to satisfy a class unlock. He can keep a dumpy orange box.
- It clears your history of hosting Class World sessions. You keep all of the benefits you did get, though - aptitude bonuses and the results of class.
- It gives you a chance to change class if you're not a Story Character. This provides some of the largest benefits of reincarnation, as it lets you get new specials and Evilities that aren't normally accessible.
- It clears all of your remaining Mana. This is not a good thing in itself, but rather an important consideration.
- If you're not a Story Character, it doubles the cost of your next reincarnation. So reincarnate wisely, otherwise it's painfully expensive.
For both story characters and your generics, if you are doing it for the stats then you probably want to hold off until late-game. At that point, you'll not only be a higher level, but also you'll have found better stages to train your characters up. The effect of reincarnation will be much more pronounced at that point, and the "catch-up" won't be as bad. So until that point, you probably won't reincarnate for the purposes of stats. It's very much player preference for this - grinding your stats and maxing everything out is a taxing and monotonous process. So this becomes more of a matter of how often you do it that'll still make the game fun to play for you.
For the rest of this answer, we're going to address reasons for reincarnation besides stat benefits.
Story characters cannot change class, and likewise their access in the Evility shop won't change. So the primary benefit for Story character reincarnation is for the Class World reset - their only means of learning new specials and Evilities. So for them, unless you really feel like starting at Level 1 (perhaps you overlevelled in the Item World and didn't feel right in squishing the plot battles on your first playthrough?), you probably want to hold off on reincarnating Story characters until, at the very least, you've hosted all possible Class Worlds.
In terms of efficiency you should also wait until you host all possible Class Worlds for generics, but that isn't as critical an aspect for them as it is for story characters. Their critical aspect is in class changing, where the guideline is more of a "When I'm done with this class for this character". This consists of unlocking the next Tier as well as picking up any specials or Evilities that you want.
You only unlock the next tier of a specific class by training as the previous - training a Fighter unlocks Warrior, while training a Warrior will unlock the next tier. Since access is permanent after unlocking, it's pretty much a waste of time to not reach the unlock level prior to reincarnation, unless you're positive that you'll never be using the higher tiers of that class. Finish that and it's a matter of completing your special and Evility learnings. How "complete" you need to learn them depends on your intent.
With the exception of Skulls and Mages (whose first four tiers can learn powerful unique spells that aren't learned by the higher tiers, among other things), each higher Tier has the ability to learn the same specials and Evilities of the previous tiers, as well as possibly gain access to new specials and Evilities not available to the previous. So if you plan to reincarnate into the next tier of the same class, then you don't need to worry about earning enough Mana to buy all of the specials and Evilities that you want. But if you reincarnate into a brand new class, then you want to wait until you learn all of the specials and Evilities that you will want on that character, as you may not have access to them in the new class. Going back is possible, but that is costly in both Mana (which increases in cost) and time, so it really works best to wait until you're "complete" with a particular class before advancing.
You should bother with reincarnating to the higher tiers because that unlocks access to the following tiers that are even more powerful, but you'll be needing to do this with all of your brand new classes as well. You can always create a new student to fill in whichever role you didn't pick, so which one you reincarnate into largely depends on just what you want that particular character to train as. Myself, I eventually tired of my Fighter being an axewielder, so I made him into a Bone Dragon. It was quite satisfying to do so.
One final note... because reincarnation resets your Mana, then even if you've reached "completion" for your character, make sure to spend as much excess Mana as you can past what you need to reincarnate. Buy specials and Evilities that you don't care for, boost the specials you do have, or host Homerooms if you still have them. There's a lot to spend Mana on, so no sense in wasting it. Even if you'll never use some of the specials/Evilities that you gain access to on that character, buying them allows you to trade them around with the Class World. This doesn't change the timetable as much as the others, but it nevertheless does affect when you should reincarnate.