It is very very hard to tell what is going on with Great Leaders from small samples. Even playing 10 games wouldn't give enough information to be sure of what is happening.
The problem is that the numbers involved (if everything is indeed working as it is supposed to) give a wide range of "normal" results. For example, if we haven't built the Heroic Epic, then we have:
A 6.25% chance of getting a great leader in the first battle won with an elite unit.
A 6.23% chance of not getting a great leader in 43 consecutive battles won with elite units.
Both of the above results (getting a leader right away or not getting one from 43 successive elite wins) will I think feel like exceptional events. But they aren't all that exceptional - they are likely to happen to any player within a few games.
To make matters worse, we are not dealing with really large numbers of this event, i.e. of getting leaders. It is not the same as battles which happen hundreds or thousands of times in a game. We expect to get a relatively small number of leaders. So each player's experience doesn't consist of a high enough number of leaders to start becoming average overall. It is a bit like flipping a coin once. You don't get 50-50 heads and tails, the number of flips is too small for statistical averages to come into play. The number of leaders we tend to get is too small, compared with the high unlikeliness of them (1/16) to expect a good statistical result in any given game or even in a few games.
I don't think that leaders are less likely in early eras. (A couple of recent examples: In my GOTM6 I got a leader from my second elite win, with an Elephant. Recently in the Game of Democracy a leader appeared from a win with an Immortal.) I think it is probably just chance, that it sometimes looks otherwise because there is a such a wide range of "normal" behavior for getting leaders. If there is anything which makes them more or less likely (aside from Heroic Epic) we'll have to collect an awful lot of data to know that it is so...