A good way of thinking about it is to find the natural breaks - such as transitioning from the main menu to the start of the level - and this is where you can delete and load media, as the player will expect a bit of a pause anyway.
Normally I split the media up in the following way (pretty much as Phaelax has described):
intro media - deleted when the player exits the intro and goes to the main menu
main menu media - deleted when the player starts playing the game
media that is used throughout the entirety of the game (bullets, explosion sound effects) - is only deleted when the player exits the game and goes back to the main menu
level specific media (map, npcs) - deleted when the level is over
It really depends on how much is being loaded. Sometime you can just load everything before the splash screen and it's quick enough not to cause an issue.
