Leveling with:
-Exploration Missions. For Lieutenant the XP output is a bit low, so there you probably go faster with normal story content
- Patrols. Patrols will give you XP for every single patrol and for completing the whole mission. They are mostly space combat or scan 5 missions, so fast and easy XP. Go get a VA friend, invite him, let him match your level and go with elite mode, this will give you a lot more XP. For KDF this can be done with the Pi Canis sorties and Empire Defense. Empire Defense will give good XP the first time you do them, after that you'll need more rounds to finish the mission, which takes time.
- Q double XP weekend
- 1 and 8 hour Skill boost: buy them cheap from the exchange and use once you hit Commander. Before that the skill points you get are quite low, so would be a waste. If there's a Q weekend you can start using them from the beginning though.
- Red Alerts: That's the best of all. Once you hit Lt. 6 go fight Borg, but make sure to be always on a team. If nobody invites you, start 1 yourself. Some people claim that lowbies should stay away, but the RAs are made for leveling. The team thing is important here, or you won't get any skill points for kills due to your low firepower. Do NOT go probe farming, try to help win the mission please

- Featured Episodes. The first time you do them is ok, most of them are longer than exploration missions, but if you hurry it's ok. After that, Cold Comfort and Spin the Wheel are good for quick XPs.
Normal storyline missions are usually not that good for fast leveling. They tend to be longer (which on its own is a good thing, contentwise) but some give decent XP, so it depends on the mission.
Just remember, don't go solely for Red Alerts, you'll only get a small amount of Merits to train your officers out of them.
Edit: Forgot 1. Once you unlocked them, do your dailies. They are fast and easy.