I don't have much experience beyond Network Solutions but have never had any problems with them (after nearly ten years as a client). A quick search of their site made me think they support PayPal. Not sure what dynamic DNS redirection is so can't answer you there. I imagine there are cheaper alternatives but so much of the Internet is fly-by-night that I've never really been tempted to take a chance on any of them. Doubt this helped much but I hope it did.
Edit: They do bug you to death to renew, though. I got my first notice today for a domain that expires in January of next year. As you get toward the final month the notices get rather dire.