The Wiznet w5x00 (5100, 5200, 5300) series based shields is what you want. They have a built in TCP/IP stack, which relieves code and ram intensive programming to to ethernet chip, and simple spi interfacing. The w5100 is what is used in some standard arduino shields. The w5200 is newer, has a sleep mode, and wiznet provides changes for the arduino library to make it work with existing code. And the w5300 is the newest, has some bottleneck fixes, but no specific to arduino library is provided yet, though I doubt it would take much changing to get working.
The key part of this being that the built-in tcp/ip stack offloads the heavy lifting from the attiny to the ethernet chip. The ENC28J60 and similar do not have the embedded tcp/ip stack, so you have to code (or use a library), and those libraries are memory and code size intensive.
A comparison, I can't find any attiny ethernet projects, but there is a w5200 based msp430 Launchpad booster pack (Shield equivalent) that targets a msp430G2553, which has 16kb of code space and just 512b ram. Example code includes a fully working server. It uses 4.5kb of code, and 400b of ram.
On the other hand, a ENC28J60 based shield and library has a code space usage of 7KB and 520 bytes RAM, on a arduino atmega328p.
Using the w5x00 (or another with a built in tcp stack) and you should be able to fit it on a attiny85 (8kb code space, 512b ram)