Search is definitely the main thing that needs improvement. Everything else I think would be best handled by plugins (and in some cases already is).

I agree that the default WordPress pagination options are rather limited but I think that enhancing this with a plugin (and there are some decent ones already out there) is the better way to go.

That said, most of the paging options out there require you to tweak your template files so that you can display numbered pagination instead of previous/next. This is usually because the 2 previous/next functions need to be replaced with a single pagination function to provided numbered paging. It would be good to remove this barrier for non-developer users somehow. Maybe it is already possible to do this with the current hooks but I have not seen an example of this or looked into it.