Increase the threshold to list views
Currently, SharePoint Online has a threshold of 5000 items for a list view. While I, as a technical person, understand that the limit is to avoid performance penalties, the customers have a hard time understanding why SP is marketed as having the ability to store millions of records, but they can only manage 5000 items at once.
Either increase the number or figure out a way to solve this limitation from the user's point of view. Saying "use search center" is not enough, as the users are expecting an Excel-like behavior to filter their information. Search, by definition, requires having something to search for in the first place. And creating custom refiners is a pain (why can't just I click on a column and select an option labeled "refine search by this property"?) and well beyond the skills of an average user (and even for tech support!).
Or, alternatively, stop fooling the customers and acknowledge first hand that they won't be able to manage more than 5000 items per list...