"If you're aiming to make it smaller than a UNO then you have a compromise to make between size and difficulty."
Smallest is best for this application, when you say it will be difficult do you mean impossibly difficult or just pain in the butt difficult?
Yeah, but how small do you NEED? Put another way, how big would it need to be for you to reject it out of hand?
If you can use a UNO footprint that means you can use any of the standard shields - they will just push on top of the UNO and you will run the example sketches and have something that more or less works out of the box. If that is too big you have a much more limited choice of hardware and may need to integrate your own solution. It's all doable, but the time and skill required increases significantly.