The first company gave you a verbal offer, which is nothing more than that. You told them that you are available at their preferred commencement date. This is just an information, which was valid at the moment you gave it to them (and still is). They know that you could be hired and start at this date.
This does not guarantee that you actually will accept that offer (and they know that). If you get a better opportunity soon, there is no problem in declining the first offer.
In this case you should however call the first company and tell them that you would have really liked to work for them, but that you got another offer which was even a better fit for you (or more convenient for you). Therefore you would like to thank them for their offer, but unfortunately decided to decline it.
EDIT (due to comments from the OP): If you are not sure about having verbally accepted the offer or not, it is a good idea to call the company and ask them about their understanding regarding the status of the offer. You might wait until you have got the offer from the other company, if you think you will get this in the next one or two days. If the first company tells you they expect you to start working on the date you discussed with them, you might want to clarify that there was a misunderstanding, and that you understood it merely as a question whether you would be available at that date.