How can I have the user instantiate an object?
You seem like you are almost there. Allocate the objects using new and free with delete.

// Abstract parent
class Playlist {
    public:
    virtual void playNext() = 0;
    // etc.
};
// Derived classes
class Something : public Playlist
    public:
    void playNext() {
        // your code here
    }
};
class SomethingElse : public Playlist
    public:
    void playNext() {
        // your code here
    }
};
// More derived classes......

// A pointer of the current program
Playlist *play_list = nullptr;

// A factory function to create a Playlist while also freeing previous
Playlist * create_playlist(int which_program) {
    // Important - delete old
    delete play_list;
    play_list = nullptr;
    // There are only 16 types, use a switch or if
    switch (which_program) {
        case 1:
            // Create a new one and save in global ptr
            play_list = new Something;
            break;
        case 2:
            play_list = new SomethingElse;
            break;
        // More cases here.....
    }
    return play_list;
}


[edit]--------------------------

Ok. The issue is that C++ does not have a lot of reflection options. So you can't create a class only by its name (as a string). Here's another solution I came up with. It's not completely automatic as it involves registering each class in setup. But I think it's close to what you want:

class Playlist;  //Forward declaration

// Each class will have a function to create itself
typedef Playlist * (*CreateFunc)();

// The parent class. It also holds a list of all child classes
// Could probably refactor into 2 separate classes
class Playlist{
  public:
  // Need virtual dtor
  virtual ~Playlist() {
    delete last_created;
  }

  // Put all the overridable function declarations here
  virtual void playNext() = 0;

  // This has to be called for each child. (See macro below)
  static void register_class(int id, CreateFunc f) {
    all_maps[num_maps].id = id;
    all_maps[num_maps++].f = f;
  }

  // Factory method to instantiate an object
  static Playlist * create_playlist(int id) {
      // Delete old pointer
      if (nullptr != last_created) {
          delete last_created;
          last_created = nullptr;
      }
      for (int i = 0; i &lt; num_maps; i++) {
          // Search the list for name match
          if (id == all_maps[i].id) {
              // Call the creation func
              return all_maps[i].f();
          }
      }
      return nullptr;
  }
  protected:
  // A struct to hold the class name and a pointer to the creation function
  struct Map {
    int id;
    CreateFunc f;
  };
  static Map all_maps[32];
  static int num_maps;
  static Playlist* last_created;
};
// Static declarations
Playlist::Map Playlist::all_maps[32] = {{0, nullptr}};
int Playlist::num_maps = 0;
Playlist* Playlist::last_created = nullptr;

// Example child class
class Child1 : public Playlist{
  public:
  void playNext() {Serial.println("Child1");}

  // Must have this function and it must be static
  static Playlist * create() {return new Child1;}
};
// Another example
class Child2 : public Playlist{
  public:
  void playNext() {Serial.println("Child2");}
  static Playlist * create() {return new Child2;}
};

// Helper macro to simplify registering
#define REGISTER_PLAYLIST(id, name) Playlist::register_class(id, &amp;name::create)


void setup() {
  Serial.begin(9600);

  // This must be done for all classes
  REGISTER_PLAYLIST(0, Child1);
  REGISTER_PLAYLIST(1, Child2);

  // Example usage
  Playlist*p = Playlist::create_playlist(0);
  p-&gt;playNext();
  p = Playlist::create_playlist(1);
  p-&gt;playNext();
}

void loop() {

}


I just whipped this up. Probably room for improvement....