Never been to Spoons, but I hear it's excellent (and pricey.)
It's been a few years since I've been to Eucalyptus - ok food, but nothing special.
For Jerusalem, I'd recommend La Regence (also pricey), Angelica (a personal favorite.) If you're looking for something "different/unique" try Racha - Georgian food. We really enjoyed it. Not overly expensive, and probably better than Eucalyptus. There's also Scala in the David Citadel. And Canela can be good as well.