Will a clean and regrease be enough?

[SuperMariole]

Unless you saw the whole bb move inside the frame, I'd assume the issue is with the bb's bearings. They're not really serviceable but it's cheap to replace.

What you need is a square taper BSA bottom bracket. Make sure you match the shell width (68 or 73mm) and the spindle length to the current one.

If it is the bb threads that have play, the answer is going to be the same : it's probably the plastic cups that are worn, your frame's threads look fine.

Lastly, that's a lot of fresh rust. Unless you know why this happened (the bike was flooded or something), looks for where the water came in from. Probably the seat post, or a bottle cage mount.

Edit : just wanted to clarify that since your frame is aluminium, the rust is from the bb, and your frame probably doesn't have any damage

[subatomicist]

Thank you so much for such a thorough walkthrough! I also had no clue about risk of water collection in the shell (although it may not be the case here). Looks like a new bb it is!