Resulta que el GNUPlot, al exportar a ficheros .eps, les hace una caja, cuanto menos, demasiado grande. Resulta que no es difícil corregir dicho fallo, editando a mano dicho fichero.

Antes:

%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 0 0 406 296
%%HiResBoundingBox: 0.000000 0.000000 405.200000 295.100000
%.........................................
...

Después:

%!PS-Adobe-3.0 EPSF-3.0
%%BoundingBox: 50 50 406 296
%.........................................
...

Vamos, que el truco está en el BoundingBox, más info aquí.