Recommender systems are widely integrated into our everyday activities. These intelligent systems succeed in learning the user's profile to recommend movies, music, news and more. However, for designing context-aware recommendations, new challenges emerge in predicting the situational needs of the user. We prototyped Ambient Wanderer, our personalised and contextualised Point-of-Interest (POI) recommender system and experimented it with new locals, people who have recently relocated to a city. Our key findings include: sudden breakdowns during urban exploration, trust issues with the recommendations from people unlike them, feeling bored as the trigger to POI search, intent to find free activities, information needs on areas-of-interest beyond points-of-interest and the demand to build a new social life. For each of these needs, we present the implications to design mobile recommendations for urban exploration. Link to the paper - Research Article Link to the blog - Naver Labs Europe Blogpost