Cheapest option, get a sprint SERO plan (search here, if it works, for much detail). 30$ a month for phone and data plan. Now, TECHNICALLY, it doesn't include PAM or tethering, but it works fine, and there are free and 20$ programs that simply do it for you over the phones data connection.

I use a sprint mogul FAR, and BT to connect to my computer, and get about 1.2mbs connections, 400kps upstream. For the past two years, do between 250mb and 3GB a month in data transfers with no problems. I have acutally never heard of anyone with problems doing this type of cheap laptop data.
This phone does GPS, reva data, takes a BT keyboard, does the slingplayer mobile justice, etc.