As for the guidance - as you have mentioned IsolatedStorage would be suitable here. In fact IsolatedSotorageSettings will be easiest I think here.
So when your App launches you should determine if it's the first run or not.
You can for example in App.xaml.cs
modify method Application_Launching, so that it will check if specific key in IsolatedStorageSettings exists if not - it means its the first run ans set up a flag.
After you know if it's the first run (or not) you can try to redirect the Navigation. I think it's well explained on this blog.
You can also try to redirect from MainPage in Loaded event (in this case you can see a blink of MainPage) - it depends what do you want to achieve.
Other way may be - not to Navigate to specific Page - but to change MainPage content, depending on your flag (if it's the very first run).