I would suggest a VS web part as this gives you great flexibility.
As far as querying the list. You have a number of options
- SPQuery or similar - runs on server (in a web part would be fine). In my experience is fine for simple queries but quickly becomes cumbersome when you add in more complex joins/filters.
- Linq to SharePoint - runs on server (in a web part would be fine). Gives you the same type of behaviour as SPQuery but in a more elegant/maintanable implementation.
- Lists.asmx web service - accessible to external clients but unweildy to consume.
- SharePoint client object model - accessible to client web pages (in a sharepoint hosted web part would be fine). Basically the client version of SPQuery - flexible but can become unweildy.
- SharePoint 2010 Lists REST service - accessible from external clients and server side code. Neat REST based API. Doesn't offer as rich behaviour as other mechanisms but cleaner and more maintanable (assuming you dont want to do much more than simple filters).
I would suggest you have a play with each mechanism. Shouldn't take too long to create a set of tests , which when you apply your business requirement to - should show you which option to take. My personal option would be 5. if it satisfies your requirement, 2 if not.
In terms of performance - all mechanisms under the hood approximately use the same plumbing. If you have serious performance concerns I would look at a cached provider such as PortalSiteMapProvider which has the same syntax as SPQuery but better performance in particular circumstances. Bottom line - as long as you are filtering on the server and not working with massive volumes of data I would concentrate on finding a working solution.