Yes, this is actually a game design feature. The palace actually provides espionage points, so as soon as you meet other civs, you can assign espionage points for counter-espionage, even if you can't do any espionage missions yourself. This is to provide people who chose different early tech paths with at least some defense against someone who rushes straight to espionage.