Here's a solution that will zoom into the map as far as possible without a custom margin. You should be able to adapt it to account for some margin if you want to.
My solution is based on this comment in a Google Groups thread. Unfortunately, the call to helper.getProjection() always returned undefined, so I adapted the above answer a bit and came up with this working code.
Just replace your existing calls to map.fitBounds(bounds) with myFitBounds(map, bounds):
function myFitBounds(myMap, bounds) {
    myMap.fitBounds(bounds);
    var overlayHelper = new google.maps.OverlayView();
    overlayHelper.draw = function () {
        if (!this.ready) {
            var projection = this.getProjection(),
                zoom = getExtraZoom(projection, bounds, myMap.getBounds());
            if (zoom > 0) {
                myMap.setZoom(myMap.getZoom() + zoom);
            }
            this.ready = true;
            google.maps.event.trigger(this, 'ready');
        }
    };
    overlayHelper.setMap(myMap);
}
// LatLngBounds b1, b2 -> zoom increment
function getExtraZoom(projection, expectedBounds, actualBounds) {
    var expectedSize = getSizeInPixels(projection, expectedBounds),
        actualSize = getSizeInPixels(projection, actualBounds);
    if (Math.floor(expectedSize.x) == 0 || Math.floor(expectedSize.y) == 0) {
        return 0;
    }
    var qx = actualSize.x / expectedSize.x;
    var qy = actualSize.y / expectedSize.y;
    var min = Math.min(qx, qy);
    if (min < 1) {
        return 0;
    }
    return Math.floor(Math.log(min) / Math.log(2) /* = log2(min) */);
}
// LatLngBounds bnds -> height and width as a Point
function getSizeInPixels(projection, bounds) {
    var sw = projection.fromLatLngToContainerPixel(bounds.getSouthWest());
    var ne = projection.fromLatLngToContainerPixel(bounds.getNorthEast());
    return new google.maps.Point(Math.abs(sw.y - ne.y), Math.abs(sw.x - ne.x));
}