If it’s Analog Mono:
The new Dreadbox Erebus 3 if you’re willing to wait a month or so, is likely to be the definition of character.
Price is €499 or so.
Obvious, and you’ve probably already considered the Korg Minilogue. At $500 it’s a good deal if you adapt to the keyboard. Has both character and versatility.
Just a little out of the price range, but similar price to the Deepmind 12 is the Studiologic Sledge.
Digital Analog. It’s also doubles as a cool multifunction controller.
Or further outside the price range the Dave Smith Mopho X4 keyboard at $1000.
I know most suggestions are probably going to push right up to your $800 limit, but I gotta throw in the Audiothingies Micromonsta at $350. Very easy to program, has some cool features of its own (for example: chord feature, highly programmable arp with randomization, user wavetable capability). Sounds great to me, I’m happy with it. It has 8 voice polyphony, not sure if that’s enough for you or not. You can also two still under your price range and they have a “link” feature to get 16 polyphony I think.
Only downside for me is no onboard note input so you have to use an external MIDI keyboard or sequencer of some kind. Also it’s monotimbral so no layering or splitting.
Analog and polyphon has never been cheap and the price depends on the polyphony. Each voice costs.
It’s also important to know, what the synth shall be used for. Shall it be a pad-machine or is a very flexible synth engine required, to use it many ways, from deep bass to soaring leads?
As a rule of thumb, the more flexible the engine of a polysynth is, the higher the price will be. Just check out the Modal 008 or the Schmidt as two examples.
If you want to create thick-classic-creamy pads, I would recommend to get at least 8 voices.
If you are content with the sound engine of the DM12, why not get it? A Prophet 8 could also be an alternative. Second hand prices should drop, because of the REV 2.
A most underated little box would be the VA-synth Blofeld by Waldorf. It would also give you wavetables, FM, and loads of modulation options for much less than $800. The Blofeld is very versatile and creates IMHO very good sound too.
It’s not just about getting a synth. You are going to want to make beats. If you want polyphony and a sequencer, you should strongly consider a Digitone or Digitakt.