Over water, probably something like the entire 60th parallel south.

Over land, I think you want to start near the westernmost point of the African continent and thread the needle of the Isthmus of Suez, and stay south of the Caspian Sea. At least in the projection gcmap.com uses (plate carree - essentially the x-coordinate and y-coordinate are just raw longitude and latitude), this keeps you south of Lake Baikal and allows you to get very far east in far eastern Russia. Something like 17.5 N, 16 W to 69 N, 178.5 E seems to work:

http://www.gcmap.com/mapui?P=17.5n16w-21.79n0.21e-26.08n16.4...

Of course this depends on the projection you use!

This is different from the Portugal-to-China path that is the longest over land in reality, which a flat-earther would have crossing the Mediterranean.