I'm not really sure why the rectangle approach would use that much CPU load, I will try this myself one of these days.
Anyway, this is a job for vertex arrays indeed. In that latest version of your code, if you call your "update()" function only when needed, it should approach 0% CPU load. There's no need to fill the vertex array with the same information in every frame, it's enough to do it when the application starts or something in the game field changes.
As for your VSync observation, yes, one is not supposed to use BOTH VSync and frame limiting, as they will get in the way of each other. This is also mentioned in the Javadoc.