The single most useful piece of advice I was ever given for fellowship essays:
These are not literature, don't write like it.An essay for a fellowship is not a novel, it is not even the standard "essay" as you were taught in high school.
You do not have to obey the simple paragraphs of text layout style. Add bold words to draw attention to your key points, use whitespace however you want. Your goal is to make things as easy for the reader as possible.
The NSF requires that you specifically address the "Intellectual Merit" and "Broader Impact" of your proposal—put in section headings with exactly these titles and write about them. You don't need "transition sentences". In this context, they're nothing but a waste of precious space that could instead say something to bolster your case; worse, as a reader, they're just crap that I have to wade through to get to the relevant parts of your essay. The last thing you want to do is annoy your reader. Think of the volumes of essays they're reading, then put away the thesaurus and get to the point.
At the end of the day, that's really the goal: minimize the crap the reader has to process to get what you're trying to communicate. Don't let the word "essay" get in your way, if a bulleted list makes the most sense, put in bullets.
Below I've provided my essays (winning and losing) as well as any reviews that were made available to me. Hopefully they can serve as helpful examples. Particularly note the change in style from my (losing) 2012 NSF, which I would consider a "traditional essay", to the (winning) 2013 NSF, which I would consider a "fellowship essay".
Fellowship Homepage: www.nsfgrfp.org
Fellowship Homepage: ndseg.asee.org
The NDSEG has fairly restrictive rules (2013 rules). In particular, you're limited to only 3,000 characters, which requires your "essay" to be extremely concise.
Fellowship Homepage: www.qualcomm.com/research/university-relations/innovation-fellowship
This fellowship is really interesting as it requires you to have a partner. I worked with Brad Campbell, a pretty awesome dude in my lab. The fellowship is (was) only open to a limited set of schools as Qualcomm grows the program. They've been adding schools every year thus far, so check the website for updated information.