If I understand you correctly you have videos and you want people to be able to find them easily without them having been put into pre-set categories such as what Netflix does.
You haven't given us much information about
what kind of videos
- Hollywood type movies;
- YouTube cute puppies and guppies;
- instructional videos - how to use Photoshop, fix your bicycle, install moulding.
nor about the users and their expectations of the site, etc...
Still, in a generic sense (and assuming here Hollywood movies and relatively savvy users) I would consider tags (as per StackOverflow).
Show a list of tags and let users filter down the movies. Example: selecting "Westerns" would display 150 choices; adding Sci-Fi to that mix may bring the choice down to 5.
Of course your movies will have to be carefully tagged; and you may want to have user feedback regarding your movies - perhaps even letting the users assist in tagging. The list of tags may become difficult to display as well. (Need more info here re type of videos).
Another option which I would consider would be a robust and cleverly created search. In this case a user could request westerns and not Clint Eastwood.
Complex searches can be interesting but it really depends on how you display it, who your users are, how well thought out your design is and how motivated your users are to explore the nuances of the search feature.
Nonetheless in order to get more feedback you'll need to provide more details regarding the videos and the users.