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.
There are some steps before getting on embedded linux. As @KKToronto said, it would be nice if you have a desktop linux experience first. If you don't have any experience I recommend installing Ubuntu in your desktop/notebook in order to get some feeling with the OS.
To go from the desktop to the embedded world, at least on linux way, is relatively easy, if you're planing to develop FOR embedded linux. Almost all drivers interfaces, kernel calls, are the same. One program that runs on a desktop linux, can run on a embedded linux with minor alterations. The beagleboard platform is a good example, as @JobyTaffey noted. Some applications I developed can run on both desktop and the beagleboard without code alterations, just need to use the correct compiler.
Still on the "develop for embedded linux" topic: one of the main alterations is the compiler, mainly because almost all embedded processors that are powerful enough to run linux are ARM ones. From the C/C++/Java programmer it is almost like migrating from x86 to ia64.
If you want to get a deeper "embedded" experience as building device drivers for new hardware, accessing I/O ports on the board, control external equipments using linux, I'd go with Linux Embedded Primer. It is a great book to learn on low level stuff as how the device drivers are made, how to get access to fixed memory locations that represent some peripheral etc. (And it has an amazing lightsaber on the cover =) )
By going on the hardware side a deep microcontroller knowledge is really important, because you're going to be dealing directly with memory for peripheral configuration/access. Some operations may even require assembly knowledge, mainly interruptions or flash writing. It depends a lot on the microcontroller architecture.
If you have no experience on this, I'd recommend to start with arduino, as @stevegt noted, to get a hardware/electronics feeling and then proceed to a baremetal programming over any other processor, to learn some tricks related to hardware/software interface, that are somehow hidden on the arduino firmware or linux kernel.
As you can see that is much knowledge hidden on "embedded linux" expression. Keep in mind that you don't need to have all of it to build an embedded system. You need to focus on what side you want to learn first and get a pre-made system for the other: arduino for hardware first contact, beagleboard to learn programming for embedded linux, a baremetal processor for hardware/software interface.
Specifically for your case I'd recommend the beagle board. As you have some programming and microcontroller background, you can develop some applications in high level to get experience at linux programming and when you fell comfortable enough you could start hardware stuff with the available I/O's on the board.
Best Answer
It's easier to tell all your devices "where the server is" than it is to tell your server "where all the devices are". It's much easier to ensure that a single server is reachable from all your devices than it is to ensure all of your devices are reachable from your server.
So normally you would have the embedded devices connect to the server rather than vice-versa. If you need to be able to request/control stuff then it's pretty easy to keep a TCP connection open continuously. Just make sure you put in place a protocol for checking the connection is still alive and if-no reestablishing it.
Depending on deployment scenarios it may be acceptable to hardcode the server address when the embedded devices are built or it may be nessacery to make that configuraable.