[SalesForce] Best way to do a count() from a custom object having more than 1 million records

Per the indexing cheat sheet PJC posted, adding and Contact__c != null to your query automatically makes it non-selective. You should remove this.

Since foreign-key fields, like a lookup to contact, are automatically indexed as long as you don't have massive numbers of time records for each contact your query should then be selective.

You're already only adding contact IDs to the conIDs if the record's contact__c field is not null, so the exta check in your query shouldn't be needed.

While it seems like a good idea to explicitly filter out nulls to code defensively this practice actually causes your query to perform considerably worse (causing a full table scan under the hood), and if in a trigger, hit this error.

Salesforce.com calculates the total amount of time it takes to process the page, including querying the database and rendering the page. Using JavaScript remoting will drastically reduce the time spent rendering the page server-side by offloading this responsibility to the client. Furthermore, using static resources instead of inline JavaScript will also reduce the calculated usage time, because data fetched from a cache (such as the CDN) doesn't count against your total server time. Consider designing your page to use the following code:

<apex:page controller="MySiteController">
    <apex:includeScript value="{!$Resource.mySiteJS}"/>
    <div id="content"></div>
</apex:page>

Your controller can be completely written as remote actions. Note that I have zero view state and only one expression to evaluate. Here's some possible code that you might use in your controller:

public with sharing class MySiteController {
    @RemoteAction
    public static SomeData getSomeData(SomeParam param) {
        // Do stuff here, return SomeData.
    }
    // More remote action functions here
}

The client-side rendering is taken care of inside MySiteJS:

(function() {
    function init() {
        // when the page loads
    }
    // Other functions here. We can also use jQuery, etc...
    addEventListener('load', init, true);
}());

Using this design structure, you should be able to get your Visualforce page loads down to about 20ms, and your remoting actions should typically return in far less than 1000ms even if you have a ton of data you're throwing down the wire. And remember, CDN (your JavaScript) is free of charge, so leverage that fact to reduce your total page time. If you're providing localization strings, I would store the languages in various static resources as well; have the page load the appropriate language pack based on the user's settings.