I second the suggestion to move up to Regent. There is a ton of information on how to play a decent game at that level and higher. It may be frustrating the first time or two, but with some tips in hand, it is more fun and more rewarding.
As for leaders, I average two or three a game (standard size map, emperor difficulty), and it seems pretty consistent. Save your elite units for attacking damaged enemies. Send in vetarans against fresh defenders to soften them up. When near the enemy, always travel in pairs to give your units a better chance against counter attacks. If you have an injured elite unit send them back to heal up to full strength before continuing. These suggestions will greatly increase the odds. The chance is 1/16 when an elite wins a battle. By preserving your elites, and only using them when they are almost sure to win, you get more chances.
One other quirk that I observed is that a great leader seems much more likely when capturing the original enemy capital. So I save an elite for taking out the last damaged defender. I do not know if there is any reality to this observation, but it has happened so many times, that I am superstitious about it.
Great leaders can also emerge from defense, so put elite defensive units in a place where they will get attacked and have a high chance of winning.
As to what to use a leader for, here is my list:
Forbidden Palace
Sistine Chapel or J. S. Bach
Build an Army
Universal Suffrage or Hoover Dam
United Nations