I think John Howe is pretty much the undisputed master of straight-up high fantasy art:
There was an 18th century Italian guy called Piranesi, who did these amazing phantasmagoric drawings of impossible 'prisons', and which were obviously a big influence on Escher:
Nicholas Roerich is worth a look, too.