Para executar um serviço quando o celular for ligado tem que registar um *BroadcastReceiver* que responda à *action* `android.intent.action.BOOT_COMPLETED`.  

No *AndroidManifest.xml* registe o seu *BroadcastReceiver*:  

    <receiver android:name="aSuaPackage.StartUpBootReceiver">
        <intent-filter>
            <action android:name="android.intent.action.BOOT_COMPLETED" />
        </intent-filter>
    </receiver>  

Adicione esta permissão:  

    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />

Defina o *BroadcastReceiver* que irá lançar o seu serviço:

    public class StartUpBootReceiver extends BroadcastReceiver {
    
        @Override
        public void onReceive(Context context, Intent intent) {
    
            if (Intent.ACTION_BOOT_COMPLETED.equals(intent.getAction())) {

                // Chame aqui o seu serviço
            }
        }
    }  

No serviço defina um método para registar as notificações.  
Este método usa o *AlarmManager* para lançar um *BroadcastReceiver* que irá criar as notificações na data/hora especificada no paramêtro *data*.  
Chame este método por cada notificação que desejar criar.

    private void AgendarNotificacao(Date data) {

     // Obtém um novo calendário e define a data para a data da notificação
        Calendar calendar = Calendar.getInstance();
        calendar.setTime(data);
    
     // Obtém um alarm manager
        AlarmManager alarmManager = (AlarmManager) getApplicationContext().getSystemService(getBaseContext().ALARM_SERVICE);

     // O id a ser usado no pending intent
        int id = (int) System.currentTimeMillis();
    
     // Prepare the intent which should be launched at the date
        Intent intent = new Intent(this, CriaNotificacao.class);
    
     // Obtém o pending intent
        PendingIntent pendingIntent = PendingIntent.getBroadcast(getApplicationContext(), id, intent, PendingIntent.FLAG_UPDATE_CURRENT);
    
     // Regista o alerta no sistema.
        alarmManager.set(AlarmManager.RTC_WAKEUP, calendar.getTimeInMillis(), pendingIntent);
    }  

Defina o *BroadcastReceiver* que será lançado pelo AlarmManager registado pelo método anterior.
Este *BroadcastReceiver* é responsável por criar a notificação.  

    public class TimeAlarm extends BroadcastReceiver {
    
        @Override
        public void onReceive(Context context, Intent paramIntent) {
    
        // Crie aqui notificação
    
    }

Como você tem mais de um tipo de notificação passe a informação necessária para construir a notificação através de `Intent.putExtra();`