EDIT: These are pretty large lists. I would review this post: http://blogs.technet.com/b/speschka/archive/2009/10/27/working-with-large-lists-in-sharepoint-2010-list-throttling.aspx
You can configure output caching from the web.config file. Look for the section titled: To configure page output cache profile settings, here: http://technet.microsoft.com/en-us/library/cc770229(office.14).aspx
Object Cache is more around navigation and cross list queries. It doesn't sound like it's going to help with this particular issue.
Output cache is what you are looking for. It will cache the page and should improve performance.
You could use the CQWP and object cache to accomplish what you want, but normally CQWP is used to aggregate content over multiple lists and libraries and to present this content to the user in a single, unified view. With that in mind it would be best to stick with the default list view and enable output caching.