Any Firewall these days can do NAT. SPI (Statefull Packet Inspection) on the other hand really depends on each vendors definition of it.
I used to work for WatchGuard Technologies on their Support Team. They make a good firewall with exceptional support. For your indicated price range they offer SOHO units. The primary advantage that you get with a WatchGuard product is that they are extremely easy and almost intuitive if you are familiar with TCP/IP.
Most if not all mainstream firewalls use a modified version of the Linux or Unix kernels. They all have the basic NAT/PAT capabilities and what you pay for is extra fluff and support.
I personally would look into an opensource Linux solution. Check out
http://www.smoothwall.org and take a look at their feature set. It has an extremely good track record and is backed by a profit earning company. You really can't beat the price, free.
If you absolutely require a paid for firewall I'll give you some good leads, but check out smoothwall first.