Smallest PIC which the TCP/IP stack can be implemented
If you're going to use Microchip's TCP/IP Stack, the PIC18 is the 'lowest-end' family of PICs that the software stack supports.

On their Ethernet page, Microchip recommends the PIC18F97J60. It has MAC and 10BASE-T PHY integrated.


  
  IEEE 802.3 compatible Ethernet Controller
  Fully Compatible with 10/100/1000Base-T networks
  Integrated MAC and 10BASE-T PHY
  Up to 128KB Flash
  8 KB Ethernet Buffer
  Support for Unicast, Multicast and Broadcast packets
  Programmable wake-up on multiple packet formats,including Magic    Packet®, Unicast, Multicast, Broadcast,specific packet match or any
  packet
  64/80/100-Pin TQFP Package