I find this sort of thing interesting, and when i finally decide to hide a cache i will probably do some sort of puzzle type cache like this.
In answer to your question, it would depend, does it have a theme?
I like the idea of a trail of clues... like the Da Vinci Code.... that ended up with them opening the cryptex in Westminster Abby after solving the newton puzzle.....
It would depend on how hard or easy you want to make it.
One puzzle that is here in Melbourne is you have to travel to various locations. at each point is a letter that makes up a word..... and leads onto other tasks (i have seen the cache listing it is on my to do list)
the one location i have seen here the letter is stuck to a tree. it is actually in plain view... but most people dont notice it
you could do similar. Select five locations, hide 5 wooden/metal letters, not in any particular order (especially if they form a word) and they have to go to the locations and find the letter to solve the code and the letters could be in plain sight i reakon most people wouldnt notice.
if you didn't want to hide letters, use signs or plaques. again using 5 locations
in a sign you might say if it is a street sign, the forth letter.
if it is a plaque, you might say the tenth letter of the third line.
just a couple of quick suggestions.