In paint, when you click resize > pixels and change the numbers to 512, does that mean it is the perfect size for 512 textures? and does the same go for 128 textures?

Yes.if it is 512x521 or 128x128 and not something like 128x436 etc.

If you have the pixels the same as the texture then the picture comes out nicely. If it isnt then it comes out usually blurry and not detailed.

Use gimp to resize textures, its perfect.
I used MS paint, dosent work AT ALL.
You give 10x10 resolution it comes out 467x467
something like that.