As previously mentioned, the most successful villanelles have two strong, flexible refrain lines. It is thus well worth spending a fair amount of time on your first stanza, since not only will you be repeating the first and third lines throughout the piece and deriving your ultimate 'oomph!' from finally placing them one after the other at the end of the poem, but you will have to rhyme the ends of other lines with the final word of your second line no less than five times.
Here are three sample first stanzas from my own work, in order of oldest to latest. (The final one was my submission to stillnotbored's February First Line Contest, which closes tomorrow - I highly recommend checking it out.)
the poet's tree:
a pebble from a pool of poetry
falls from the page to break my surface calm
I come to rest beneath the poet's tree
Mornings recall her to her lie
dreams washed away in the shower
and the birds sing hello, goodbye
Her bones remembered the proper shape-
though time leached their strength and weighed her eyes
she had only her sweet flesh to drape
( Further discussion and full text of 'Proper Shape' behind the cut )
Finally, if villanelles are so difficult to write in comparison to, say, a haiku or a free form poem, why would anyone choose to write them? I personally like doing them because they require so much focus and skill. The format is such that I have to completely close out the world around me for an hour or two and just give myself permission to play with words and sounds and concepts. The product may not always be devastatingly brilliant, but I surface feeling cleansed, much like having gone on a long run or having solved a difficult sudoku or having finished translating a passage from Ovid. I have put some small subset of the world in order, and it rhymed to boot.