Resize uploaded original images to a minimum automatically

From purely WordPress point of view you want add_image_size() with a “hard” crop mode. That will ensure that any significantly large image will be sized to fit into those dimensions exactly, cropping some parts if necessary.

The problem is usually that WP won’t upsize small images to fit, as far as I remember. It is most definitely possible to implement custom sizing logic, but it’s not something straightforward really.

In my opinion hard crop size is reasonable low hanging solution here. Anything that it can’t handle probably requires human attention for decent result anyway.