Depends, would be easier if you showed us your set..for cartoon sets 512 is unnecessary when it comes to the body textures the head I think should always be 512, for more complex sets 512 does look considerably better, but also is far more expensive and as I said for the more simple sets you hardly tell the difference, unless you look closely.
So basically just pick what you can afford and what fits your set and you'll be happy.