Low end pentium will definitly handle it. Our nat box is a decrepid 486.
It's running dhcp, dns, printer sharing (via lpd) 

If you're going to autodial don't use diald or similar soultions. pppd has a
quite useful demand dialing mode. Here's how I did it under Debian:

/etc/ppp/options:
# Begin /etc/ppp/opetions
demand
# Disconnect if Idle for 5 minutes
idle 300
ipcp-accept-remote
ipcp-accept-local
lock
noauth
defaultroute
asyncmap 0
crtscts
hide-password
#modem
proxyarp
lcp-echo-interval 30
lcp-echo-failure 4
noipx
user username
remotename isd.net
modem 57600 crtscts
#connect '/usr/sbin/chat -v -f /etc/ppp/call-isp'
connect '/usr/bin/pon'
# End /etc/ppp/options

It's been a long time since I've had to use this, so no promises as to
wether it works or not. 

As for NAT compatiblity, we have no problems playing quake3, UT, StarCraft,
etc on one IP. Linux IPMasq has modules to get full functionality out of
other apps (irc, icq, quake and quake2, etc...) and ipautofw (or whatever it
is...) should handle simple stuff. Some games may still require special
ipchains rules, most of the documentation I've found is for 2.0 kernels
though. 


-- 
| Andrew S. Zbikowski       | Home: 763.591.0977 |
| http://www.ringworld.org  | Work: 763.428.9119 |
| http://www.itouthouse.com | PCS:  612.306.6055 |
|   "If there's anything more important than my  |
|   ego around, I want it caught and shot now."  |