This is probably not as inexpensive as you wanted, but I have used the Linksys WAP54G on the client end, and a WRT54G on the internet end for wire-to-wireless-to-wire links. It worked well, but it helps to be familiar with router setup and routing.
How far is the Arduino from the wired internet connection? That may help determine which devices will or will not work for you.