Nick here from Shopify.
Really good question. Like yourself, I did some digging through some of the more popular discount apps on the Shopify app store looking for this feature. While I couldn't find any that outright say they do this, there is a way this could still work for you.
Natively in the Discount section of the admin. You can limit the usage of the discount code to once per person as seen in the image. When this is set up, you could then use a pop up or an email to notify first time customers of this. One app I saw (which is also free) for this which seems to do it quite well is the Popup Upsell on Exit &Visit app. What struck my eye on how this could work for you is this section here: With the discount code only available to each person once and both aspects being free, hopefully, this is something which could work going forward.
Don't hesitate to ask should you have any other questions.
All the best, Nick
I think you may be able to do this natively using Nick's advice with addition of using a Customer Saved Search. You could create a saved search on Customers who have 0 orders and set your discount customer eligibility to "Specific groups of customers" and select that saved search you created.
Hope that helps!