Category display (and category/tag search)

I’m finding the Category display widget to be a dead end to the user’s navigation. It will show only categories but I’d like that once you click on one category it would show a list of the posts inside that category. What I’m getting now is just a couple of posts in that category getting shown (maximum blog posts per page allowed) and the only way the user has to find more is by clicking on ‘older entries’. Is there a way to provide with a list of posts once the user clicks a category?

I’m finding that the basic wordpress search widget in wordpress only searches for tags and not for categories. I’d like to search for categories and categories with tags too. Is there any solution to this?

thanks