What are your requirements (both minimum and goal)? Size and preferred interface are both important.
There are plenty of truly tiny memories out there, some even below 1 mm². But the really small ones can't store much: there's both a die size limitation and a minimum pin count for the interfaces on the larger (parallel) memories.
The 5 mm×6 mm size serial flashes are quite common, with options from many manufacturers. There are also several available in 2 mm×3 mm, but the selection there does decrease.