Going in (Great) Circles:
On a spheroid like the Earth, it is a well known fact that the shortest path between two points lies on a Great Circle. What is not so well known is that this same Great Circle also defines the longest distance between those two points. The longest distance is simply the arc going the other way.
So, my question was: "what is the longest great circle route one could fly on Earth and always be over a) land, and b) water?"
Thanks to Google Earth and its Ruler/Path tool, I found the following candidates:
Over Land: Beach near Dong Hoi, Vietnam to Dakar, Senegal - 12,900 km
Over Water: Tellicherry, India to Iliamna Bay, Alaska - 29,000 km
You will note that for the overland route, I did not count small lakes as being over water. The key to this route is threading the arms of the Red Sea and the southern Mediterranean beach near Rafa. If you slightly bend the "rules" and ignore the arms of the Red Sea, you can get a much longer route, Magadan, Russia to the Northern Namibian coastline (Hoarusib Mündung/Delta) of 14,620 km. This route is constrained by the Caspian and Black Seas.
For the overwater route, I did not count very small islands as being over land. Getting around Antarctica is the key to these routes, and threading various narrows. This is where you will have to use the 'path' tool rather than the 'line' because these distances are farther around than the antipodal point. An early candidate of mine was Pulau Dramai, Papua New Guinea to Seminole Shores, Florida - 24, 460 km.
Have at it folks!