So what should I do - focus on losing weight with a small calorie deficit (say 500 cals max) and just try to maintain muscle mass, or should I just keep pounding the weights and eating a little over maintenance cals??
As seiux said, for a beginner losing weight (losing fat) and adding muscle are almost the same thing. Now to answer your question specifically;
1. No, you do not absolutely need* to go with a small calorie deficit to achieve your goal of losing 15lbs. It is okay to eat the proper calories for your body. From what it seems at this point in your health it would be better to focus on the quality of the calories instead of the quantity.
Need* = You can achieve your goal without a calorie deficit but the same way you calculate how many calories extra you need to gain weight you can also do the same for losing weight. Last recollection was 3500 calories per pound of fat. (Just a marker to reference.)
What matters is making sure that you are reaching the heart rate you need to be in to achieve your goals, eating foods that give your body the vital nutrition it needs, drinking the proper amount of water and appropriate rest.
If you do not have a heart rate monitor, purchase one. The Heart rate monitor will help you in your HIIT training. You can spend a little or a lot, it is up to you. The Omron HR-100C gives you good value for the price.
Using a heart rate monitor allows you to properly track your workout and to help make sure you get into the "zone". It is not "needed", but it is a very helpful tool. If you do not get into the proper zone during HIIT sessions you will spend months in the gym and not see the results you want.
Back to the food intake; it's all about proper food! Some say six to seven meals, some drink tons of protein shakes, others go raw and some go vegan (good but takes a bit of creativity on the meals). All options work, but all may not work for you.
Find what works for your body. Take the time to learn your body. Do not give up. It can be difficult but knowing what works for you helps you reach your goals.
Most important is the quality of the food you eat, not the numbers of times per day or the number of calories; unless you are a professional bodybuilder getting ready for a competition.
Regarding diet you can double up on your vegetables and have less potatoes, rice, bread and pasta. When you are hungry drink a glass of water or more to relieve the feeling. Yes, people do lose weight or become muscular while eating hot trash, but that may not be you. Kill the junk food. Eat fresh fruit (in moderation) vegetables or other "snacks" instead of hitting McDonald's, grabbing a Payday, a Snickers or a bag of Doritos.
Some of this you may already be doing and if so keep it up. The last ten to fifteen lbs are the pounds that piss off everybody. Without all the specifics it can be somewhat daunting to put conceive an accurate way to assist you, but hopefully these basics can be of help.
If you belong to a gym that offers either a cycle or spin class enroll and go religiously. With a good instructor you will get results in a month.
Oddly enough my mate is in the other room doing Ab Ripper-X right now.
Wish you the best. A healthy body is a great reward to have.