1. Any search keyword works. The lag is most noticeable when you have universe enabled since there are more packages to search. It is also most noticeable when you first use synaptic after you boot, since the information about the packages isn't cached in memory.
2. I don't have an accurate timer, but it's about 4-5 seconds. The time of the search isn't the issue, it's the fact that the search is done on the UI thread.
3. Core 2 Duo T7500 @ 2.2 GHz, 4GB Ram, 120GB disk
The issue is that any processor intensive task should not be run on the UI thread, since the UI thread should always be responsive. Canceling is an example of why you want a responsive UI thread.