John said that his records are better than or at least as good as hers.
John said that his records are at least as good as hers.
These two sentences mean the same thing, but the first expresses more boldness; John is making a bold claim that his records are better. The second sentence is less bold, simply saying “as good as”, which may actually betray some doubt on the part of John as to the quality of his records.
You wouldn’t use any variations of “at their least”, as they imply that in objective reality the records can vary in quality, whereas what we’re really talking about is difference in subjective opinion. We’re trying to gauge their actual worth, which is not something that can vary.