Is there any module that comes with CB where you have an option for other users to search each other? And that you can add any search criteria?

Not a module, but you can create Joomla menu items of type "CB UserList". Lists can have different access restrictions. You can build lists with up to 4 columns. You can add multiple fields per column. Lists can start in view-mode or in advanced search mode. The latter will open the search and filter form automaticly.

For some demos just visit:
templates.joomlapolis.com/demo/mycommunity/j15/index.php?option=com_comprofiler&task=usersList&Itemid=55

In the upper right corner you can switch to different lists. The first has NO search form. The others show their form after clicking on button "search users".

Thank you pepperstreet! That's what I was looking for. Cheers!