The challenge difficulty definitely scales between different searches. For Advanced Skills, I'm pretty sure they're Narrow difficulty 6 on the Third City search and Narrow difficulty 10 on the Second City search, but I don't know about the main stat challenges, so I'll just share the data I have. I've got total Watchful 204 and I have a 68% chance of success in the Watchful challenge.