So what should the first kind of battle ready ships be like? How soon can I expect need for them?
How soon you will need them depends on how you set up your game. If you had NPR's generated at the game start then they will start exploring and can come across you, or if you have invaders turned on you could be attacked at any time. If you have no invaders and no starting NPR's you are perfectly safe until you start exploring outside of your home system when you can start triggering new NPR's or other threats.
Most people tend to go with missile ships for their early combat designs as it is relatively easy to make a decent range and speed missile of size 3/4 even at very low tech levels. What design to go for however is very much influenced by what tech you have available if you allowed the game to pick your initial techs, and also on whether you want to go for numerous cheap small fragile ships or larger more heavily armed/protected but fewer in number ships.
You would probably be well served looking back through the thread as there have been many, many designs posted here previously, or look in the ship design section over on the aurora forums.
I keep getting messages that my PDCs are out of fuel. Anyone know what that might mean?
You shouldn't be getting this if you have no fuel tanks on the PDC. If you do have fuel tanks(eg for a hangar PDC) they can be refilled from the planets stockpiles via the miscellaneous tab of the individual ships screen as you can't give PDC's orders via taskgroups.