A textbook 32-bit RISC processor core capable of running the no-mmu version of linux doesn't actually need to be that large - the real resource you need is far more RAM (10s of megabytes) than available in any FPGA, so you'll probably want SDRAM on the board and a controller for that in the FPGA.
That said, if you want anything more than a trivial level of performance, you probably want a core with some optimizations (pipelining, etc), and that starts to increase the size somewhat. Adding a full mmu will make memory (re-)allocation more efficient and enable the usual copy-on-write fork() behavior.
Both major FPGA vendors have soft processor cores with available linux ports - Microblaze for Xilinx, Nios II for Altera. You should probably read their docs for specific platform recommendations as it is of course a target that moves with time. A third party core design might be somewhat larger for similar performance, if it is written in a more portable way and not as specifically optimized for a given FPGA family.
Historically there have been chips available combining both a hard processor core (often powerpc) with a region of configurable FPGA fabric. Another option to look at would be a separate processor (likely ARM) on the same board as an FPGA.
A lot of the decision will depend on how tightly you need to couple the processor and FPGA. If you can reduce the problem to configuration registers and a stream of data, it could be as modular as hanging an FPGA board with a fast USB chip off the USB host port of an embedded linux board like a BeagleBoard or RasberryPi. For tighter integration, you may want the FPGA on the same board and sitting on the processor's external bus. Or for low data rates, it's trivial to put an SPI register interface in an FPGA, and UART interfaces are entirely do-able though a bit trickier.
Finally, there is the question if you actually need a full operating system such as linux, or if a more "micro-controller sized" embedded TCP stack would solve your problem while requiring less memory.