The biggest difference in trucks between Uhaul and Budget that will be of concern for your trip is the number of seats. Uhaul trucks have 3 seats in nearly all their trucks (the smallest, 10ft truck might only have 2, but I don't know if I'd want to tow with that truck anyway.) I believe with both Budget and Penske you have to be using their largest trucks before you get a 3rd seat.
If one is significantly cheaper than the other, the companies will usually be willing to price match.
While I think you could safely tow your minivan on a tow dolly, I think you'll find it is much easier to get the full sized trailer. As GLC mentioned, with a tow dolly you can't back up at all, which can be a big pain on a long distance trip like this, and just in general, the full sized trailer is going to handle better.