Nah, phone manufacturers are pretty much still sticking with Android. If a Linux-based device exists, it's usually relegated to a low-volume fringe status, rather than being promoted + widely available.
Linux being used on other entertainment devices (TVs, game consoles, etc) is more normalized, but hasn't been able to trickle down to phones. Applications make or break a phone OS's adoption; see the failure of Windows Phone (and Windows RT) to gain traction. On other devices, though, all you really need is a few smart apps & you're good.
As for phone size, even 4.5" (for the screen) is the typical minimum for budget phones from well-known manufacturers. I don't think you'll see 4.0" (screen) as an option for too many brands without going for older devices, which defeats the purpose of upgrading.
Depending on your service provider, you should be able to see what they offer & decide if anything is worthwhile. If nothing, maybe you can find a device compatible with your networkâ€¦but that requires a little more work.