It will if you play on Tribble (the F2P test server) because storyline missions get you more SP than they do on Holodeck. However, I don't think it's any faster if you just do storyline on Holodeck and the patrol missions add quite a boost to your total SP (about 1/2 the SP you get on storyline missions.)
So I have started on my second toon, the first playthrough I did everything. This time I just want to hit VA as soon as possible. Does anyone have any suggestions for pure speed leveling?
I was thinking of just doing ONLY missions, no patrols, no exploration. I am not sure if this will cause an increase in leveling speed though?
If you have no interest in the patrols and story missions then the easiest way is the Klingon levelling experience; Skirmish, Spin the Wheel, Cold Call and Cold Comfort. Just repeat as many times as needed until you hit level cap. Although it's really very boring it's also very effective, especially if you drop into any Borg DSEs you come across along the way as they give a lot of XP if you're teamed.
Militis is correct, especially with Spin the Wheel and Cold Comfort. They can be done in close to 5 minutes, with each mission granting a nice bit of EXP (365 at Captain/RA I recall correctly). So you can just cycle through the missions he listed for quick and esy levelling. Although if you don't fancy much combat, try doing Cold Case instead of Cold Call, since it's a nice easy 'scan x' type mission in different systems.
To level my characters quickly, I did the following:
Do all the Breen featured episode missions.
Do the Breen/Deferi Dailies.
Do the Devidian featured episode missions, up until Spin The Wheel.
Do the Traelus satellite daily.
Do current level specific defend X sector block.
*don't turn any mission in*
Buy a skillboost from the exchange and use it.
Turn the missions in, with the 'defend x sector block' first.
You gain 3 or so levels easily. The only reason I didn't do missions past Spin The Wheel was that I just hate fighting Devidians (especially those phantasms)! :p Romulan featured episodes are also a good idea if you can be bothered to do them, but it is a bit of a trek between Romulan and Breen space especially at lower levels.
Just be warned though, you'll get SICK of these missions and it quickly becomes tedious. But you level quick.
The biggest thing though is planning how to tackle missions so you travel the least distance in sector space - thats where a lot of time is wasted.
The thing to keep in mind with these missions is that you end up repeating and grinding them so many times that it feels slower than it actually is. Been working on another character doing this and the grind is starting to set in, so just hang in there.
Also the nice thing about Spin the Wheel, Skirmish, and the two Breen missions (forget their names) is that they give awesome equipment for each tier. Skirmish gives a great Covariant ship shield and a purple ground shield, Spin the Wheel gives blue weapons, and the two Breen missions give purple ship engines and deflectors.