Personally, I use my 17-40L a lot for landscape, especially waterscapes, usually near the wider end. It gives a dynamic look that's different than just stitching multiple shots together, but of course that look isn't for everyone.
Others have covered many of the spots I'd recommend, but here's a few more:
Lanai Lookout on the Windward side, right off the road. Lots of signs at the parking lot telling you not to hop the fence, but everyone does it anyway. Just be careful, as the rocks can get slippery and rogue waves can crash over the rocks.
Eternity beach near the Holona blowhole.
Papa'iloa Beach - Not sure of the name, as I also heard it called Police Beach, but then someone else told me Police Beach was somewhere else...but anyway, on the north shore find Papa'Iloa road, go the end and park where you'll probably see several other cars. There will be a narrow walkway between houses to the beach. You'll probably have it mostly to yourselves, except for a couple of locals, maybe some surfers. Head to the left, and depending on tide/time of year you may see some cool mossy volcanic rocks exposed. This is where the Lost beach camp was, which we accidentally ran into. I've also seen turtles sunning here almost every time I've been there, but that may just be luck.
Makapuu Lighthouse trail (someone posted a pic from near it above, but I think named it).
Kualoa Ranch - This is a tourist spot, with guided tours. I don't like that part, but it's a pretty beautiful valley. Lots of filming has been done there and you may recognize it from shows/movies like Lost, Godzilla (footprints are still there).
Manoa Falls - Near Waikiki, up into the hills; I can't recall how long the hike was, but it was pretty easy. Take bug spray! Might be a bit crowded in the middle of the day. Better to go after a rain (but it'll be a little muddy), as I've heard it can be dry depending on the season.
Kawela Bay - Nice little bay, which I've rarely seen anyone else there except when I once ran into Lost filming, and another time into filming of one of the chipmunk movies, lol. You can make the long (but nice) walk from Turtle Bay, or park along 83 at the fruit stands. Across the road from the fruit stands is a gate with a sign about private property and no entrance, but the locals all told me that was a BS sign that Turtle Bay put up; the spot is public, but they agreed to pay for upkeep of the area, so the less people there, the less they have to maintain it. There's a short walk from parking to the water through a cool banyan tree grove (which, by the way, there's a map to from Turtle Bay, so if you're staying there they'll gladly tell you how to get there). From the bay, there's a nice walk around the NE side, through trees and around the point. Eventually you pass a small abandoned military bunker/observation building, and then hit the Turtle Bay Resort.
Olomana Three Peaks Trail - I've seen some amazing shots from it, but it looks too dangerous for me to try.
Spitting Cave of Portlock - It's hard to find, but a pretty cool spot. Might be hard to really compose good shots.
If it rains, I've heard you should head over to the windward side Kaneohe/Kailua and get a view of new waterfalls off the mountains. Not sure if that's true, I've never experienced rain there in several visits.
Someone above said to stay away from the west side because of the car break-ins. I hadn't heard that, but in my visits it defintely seemed more remote and 'local-friendly.' I'd still at least drive it and maybe take some shots near the car, as the hills and beaches on that side were pretty spectacular. I really enjoyed shooting at one of the beaches there; can't recall the name, but I think it's near the NW tip, where the road goes from paved to dirt.
Unsolicited, non-photography tips: I really suggest stopping at one of the Giovanni's shrimp trucks on the north shore, one of the shave ice places on the north shore like Waiola or Matsumoto's, and don't be afraid to check Hotwire for car rental prices. A few years ago I went 3 times, and got $9.95/day twice (midsize), and $12.95/day once (midsize, but they were out, got a free upgrade to a luxury car). Also, I'd re-iterate what others have said about being careful of break-ins; you'll see broken glass at parking spots. Besides not leaving anything valuable in the open, I'd also be careful about what people can see you doing in a parking lot, like putting valuables in the trunk where others may be watching.