Vorrei usare qualcosa come Pattern di fabbrica . Restituirebbe l'implementazione concreta del metodo di persistenza richiesto.

public class Program
{
    public void SaveGame()
    {
        var gameSaveFormat = ConfigurationManager.AppSettings["gameSaveFormat"];

        var persistence = PersistenceFactory.GetSaveMethod(gameSaveFormat);
        persistence.SaveGame();
    }
}

public interface IPersistence
{
    void SaveGame();
}

public abstract class Persistence : IPersistence
{

    public abstract void SaveGame();
}

public class SaveToDatabasePersistence : Persistence
{

    public override void SaveGame()
    {
        //Implement SaveToDB
    }
}

public class SaveToXmlPersistence : Persistence
{

    public override void SaveGame()
    {
        //Implement SaveToXML File
    }
}

public static class PersistenceFactory
{
    public static IPersistence GetSaveMethod(string saveMethod)
    {
        switch (saveMethod)
        {
            case "Xml":
                return new SaveToXmlPersistence();
                break;
            case "DB":
                return new SaveToDatabasePersistence();
                break;
            default:
                throw new Exception(string.Format("Unknown Save Method. {0}", saveMethod));
        }
    }
}

Il metodo GetSaveMethod accetta una stringa che definisca il tipo concreto che si desidera restituire.

La classe astratta Persistenza è facoltativa. Dovresti usarlo se hai bisogno di funzionalità comuni tra le implementazioni concrete. Se scegli di non usarlo, ogni tipo concreto dovrebbe implementare direttamente l'interfaccia.

Non hai specificato quale lingua stai usando, ma in .NET puoi usare ConfigurationManager classe per leggere il metodo di persistenza da un file di configurazione.

Infine

I'm hesitant to use a Singleton due to all the bad reviews I read about it, and I don't really want to have to pass this object around to every class just in case I need to save something.

non ha molto senso. Una classe Singleton viene chiamata quando necessario. Un oggetto che viene passato a ogni classe nel caso in cui sia necessario utilizzarlo, è sicuramente un'implementazione scorretta di quel modello.

public void SaveGame()
{
    var persitanceMethod = MySingleton.GetInstance().PersitanceMethod;

    var persistence = PersistenceFactory.GetSaveMethod(persitanceMethod);
    persistence.SaveGame();
}

Il codice sopra sarebbe un esempio (dalla mia testa) di come chiameresti una classe singleton per recuperare una proprietà da essa.

Aggiornamento

public class Program
{
    private readonly IPersistence _persistence;
    public Program(IPersistence persistence)
    {
        _persistence = persistence;
    }

    public void SaveGame()
    {
         var persistenceObject = PersistenceFactory.GetSaveMethod(_persistence.GameSaveFormat);
         persistenceObject.SaveGame();
    }