any item that grants a 19 or higher strength are legendary items; not common things that you find at Magic shoppe
In your games that is true, in generic D&D 19 ability granting items are classified as uncommon and seem to show up in very low level adventures. The starter set adventure has one, at least one of the organized play adventures has another, both of those are for levels 1-4 or so.
Just saying "legendary" is a bit of an overstatement, it seems pretty well expected to find some kind of stat increasing item by level 5.