I see you found some enhancement when you created a clustered index.

All my tables have clustered indexes on the primary key.

As most of the searches are against the primary key, this helps a lot. Also, when no other indexes can be found, from the execution plan, for a good performance, the clustered index is usually used.