The W5100 is well known for running very hot even in normal operation, and it's not something to worry about - it's just a characteristic of that particular chip.
Interestingly, and quite sensibly when you think about it, the W5100 isn't a pure hardware solution. It's actually a microcontroller in its own right, with its own CPU, RAM, Flash memory, I/O, etc. It runs its own firmware to implement a TCP/IP stack plus SPI comms with whatever host it's connected to (in this case the ATmega on the Arduino) so as soon as power is applied it boots up and initialises its SPI interface ready to receive configuration data from the host.
So even if you just load up Blink on the host, the W5100 is still burning CPU cycles waiting to be told what to do.