People Finder Web Part
SPS 2003 contains a search scope called People, but counter to most people's expectations this not only returns people that match the search term, but also documents, lists etc authored by those people. For very many organisations I work with finding other people in the organization is a real problem and most have built and maintain custom applications to enable employees to search for colleagues by name.
Many people I talk to see SharePoint search and the People information it makes available through the public My Site view as way to deliver equivalent functionality using an 80% out-of-the-box solution. Here's a People Finder web part that will do just that. There's nothing very fancy about this - it's a Content Editor web part with a little HTML and JavaScript in there to initiate an SPS search and limit the result set to people. However, it does enable wildcard searching.
Search for Peter Jones for example and you would get an exact match. Search for Peter, and the search results will contain people with forename Peter, plus all those with a surname Peters, Peterson, Petersen etc.
To use the web part, import it as you would normally, then open the content editor in source view and change the URL https://server_name/... to contain the name of your SPS 2003 server. In a production environment of course you should probably rewrite the web part as a fully fledged .NET web part to secure it from meddling users ;) In fact Dan started a GDN workspace for this very purpose earlier this year. However I've found that this approach is great for quickly building demos and proof of concept solutions.
If you are interested in the technical details of how this works and possibly adapting this to perform other types of search there are two pieces of documentation you will need: SPS 2003 HTTP-GET Query Syntax and documentation for the SQL Search Syntax which is in the SPS 2001 SDK.
[Updated 18/11: Added link to Dan's GDN workspace]