Were you using firewall software on your computer? If not then maybe you were letting in a bunch of traffic that the router's internal firewall has now put a stop to. Can't think of another reason why a router would speed things up really.
I bought a Treo 650 off of ebay to replace one that was stolen. I think it was under $100 at the time and was at the end of its run as a current smart phone. You might not have great luck since you are looking for a $600 phone without a subsidy.