You can do this from any building that sticks up above surrounding buildings and trees. Or, you know, pretty much any boat on the ocean (and many large lakes). You just need a narrow enough field of view — which is to say, a lens with a relatively high focal length.
For example, here is a picture from a second-floor deck, with the lens parallel to the ground:
This is at a field of view corresponding to that of about a 400mm lens on a 35mm ("full frame") camera. Now, obviously, that's not all sky, but I'm in the most densely populated city in New England, so there's buildings all around. If you're somewhere with just a little more space, no problem. Or, use a slightly longer lens.
That said, presumably you want as wide-angle shot as possible. In that case, you're looking for a) height and b) flatness below. Cliffs along the ocean are a good way to get that — here's a list of some of the most dramatic — many of which look to be great tourist destinations. Kalaupapa in Hawaii, the cliffs of Moher in Ireland, Fira in Greece….