Для приложения при запуске необходимо добавить разрешение
<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED"/>
к вашему манифесту.
Тогда делай, как писал Владимир.
Для запуска другого приложения вам необходимо знать (надеюсь, официальное) намерение запустить его. В противном случае смотрите мой ответ на вопрос
вызов действия, которое находится в другом пакете (Android)
Например, запуск приложения LastFM будет выглядеть так:
final Intent i = new Intent("android.intent.action.MAIN");
i.setComponent(new ComponentName("fm.last.android","fm.last.android.LastFm"));
startActivity(i);