In my magento instalation the template for first name and last name, in checkout, is
template/customer/widget/name.phtml
It is added in template/persistent/checkout/onepage/billing.phtml
as
`<li class="fields"><?php echo $this->getLayout()->createBlock('customer/widget_name')->setObject($this->getAddress()->getFirstname() ? $this->getAddress() : $this->getQuote()->getCustomer())->setForceUseCustomerRequiredAttributes(!$this->isCustomerLoggedIn())->setFieldIdFormat('billing:%s')->setFieldNameFormat('billing[%s]')->toHtml() ?></li>`
under
<li id="billing-new-address-form"...>
But try to activate template path hints and you will see which template is responsible to rendering this fields.