I want to offer all new customers money off their first order

You could create a one time use promotion code that is given out to the new user to use in the store. It can be for a specific amount off the order and each customer will only be able to use it one time. 

To set this go to: Sites > Promotions > Choose "once per user" and "Amount of Subtotal"
If there are a number of users being added at one time, the promotion code area has the ability to upload a database list of promotion codes, or they can be added manually as new users are added. 
For more information on this please refer to the chapter Ch. 059 Promotions