Best way to code large static maps in Apex

The pattern used depends on if you expect the map to be used or not. You have a misconception here, about "compile time vs execution time." Unlike Java, there is no optimization in Apex Code that serializes statically initialized maps. In other words, it always executes every time, and costs CPU time accordingly. The difference between the first and second method is that the first one will always cost CPU time, while the second will only cost CPU time if that property is accessed (lazy loading). However, if statements themselves have some non-zero CPU usage, so if you need to use the map a lot (say, in a large loop), the first method will have less execution time per loop.

In one extreme case I had, I had a class that was used by many other classes, and had hundreds of final static variables; we timed it and found that the class added an entire 1,000 ms to every transaction that used that class. We converted the class to the second form (lazy-loading using getters), and it reduced the average transaction time by about 990 ms for any class that used it. In other words, you should definitely avoid loading data that you may or may not use. Using the second form typically saves a lot of CPU time.

While I suppose you could use lazy loading to shave CPU time, the most consistent and obvious savings for me has always been in reducing other governors such as queries, callouts, etc.

For example:

public static Map<String, String> configData1
{
    get
    {
        if (configData1 == null)
        {
            configData1 = new Map<String, String>();
            for (ConfigObject1__c record : [SELECT ... FROM ConfigObject1__c])
                configData1.put(record.Name, record.SomeOtherField__c);
        }
        return configData1;
    }
    private set;
}
public static Map<String, String> configData2
{
    get
    {
        if (configData2 == null)
        {
            configData2 = new Map<String, String>();
            for (ConfigObject1__c record : /*callout result*/)
                configData2.put(record.Name, record.SomeOtherField__c);
        }
        return configData2;
    }
    private set;
}

Imagine if you call some static method on your class which doesn't care about configData2, you would be quite surprised at the side effect that calling the method consumes a callout. Same could be said of config1Data with the query, and if you have several of these maps, it can add up.

Another side benefit is that you can make your collections private set so you know they are not nillable. Although the same can be achieved by declaring them final.