You didn't state where you were going on holiday, but if it's warm - why not take her to watch the sunset and do it then, or whilst looking at the stars.
...huh...why are chicks always with the clichés????its pissin me off...cuz then when you start thinkin...hey chicks dig cliché ish stuff....and then theyre all like...omg...be more orginal....so then...you gotsa get a ride home...and that sucks.....