The "poor" performance of the shapefile provider is probably due to the fact that the spatial (quad-tree) index is created once on setup on first call to Open(). That may take some time on a shapefile that size.
The database providers rely on the spatial index of the database, that does not have to be created. If it is not there, it is not used.
I don't exactly know if there is a way to save the quadtree spatial index, and if so, how it work. But you may get better performance going that way.
If you want to sort out features by some attribute criteria, you are -probably- better of with database providers and setting the DefinitionQuery property. It should work out better than ShapeFile providers filter delegate method.