I’ve had success with an iPod. It’s very cheap, the size is perfect, and it’s just as fast as the latest iPhones.

It does everything a normal iPhone does (and I’ve never encountered an app that didn’t work), except you have no SIM so you can’t make regular calls, send/receive SMS, or use data. This can of course be a problem at times, so I still have a cheap backup phone that’s usually powered off, and often left at home unless I’m meeting someone or need to use Google/Apple maps. From a privacy perspective you also benefit from its lack of SIM card since it doesn’t ping cell towers.