If you're new to Magento, this answer likely will not make sense. So either get an experienced Magento developer on this or start brushing up. With that, here's what you can try.
Prerequisites
Ensure that you have defined terms in Magento under Sales > Terms and conditions
Ensure that you have terms enabled in System Configuration > Sales > Checkout > Checkout Options > Enable Terms and Conditions
And please note, these instructions may vary greatly depending on your version of Magento/checkout extension in use, and where you actually want to display the agreements. This will show you how to work it out on a stock CE installation.
How Agreements are Rendered
See app/design/frontend/base/default/layout/checkout.xml:
...
<checkout_onepage_review translate="label">
...
<block type="checkout/agreements" name="checkout.onepage.agreements" as="agreements" template="checkout/onepage/agreements.phtml"/>
...
</checkout_onepage_review>
...
The middle line tells Magento that the layout on the review step will contain a checkout/agreements block named checkout.onepage.agreements. It also sets up the template there.
So when the checkout reaches the review step, this file comes into play.
app/design/frontend/base/default/template/checkout/onepage/review/info.phtml:
...
<div id="checkout-review-submit">
<?php echo $this->getChildHtml('agreements') ?>
<div class="buttons-set" id="review-buttons-container">
...
And that 2nd line is asking to render the block we defined in the layout XML above.
How to Require Agreements at Checkout Step 1
If you've followed me so far, then you can infer to start by moving/copying the layout XML block node (checkout.onepage.agreements) into another area (called a 'layout handle') of the same file. Find the layout handle checkout_onepage_index, and get to its child block named checkout.onepage.billing or whatever block you want to display the agreements. Extend it by adding that agreements XML, so that it looks like this:
...
<checkout_onepage_index translate="label">
...
<block type="checkout/onepage_billing" name="checkout.onepage.billing" as="billing" template="checkout/onepage/billing.phtml">
<block type="checkout/agreements" name="checkout.onepage.agreements" as="agreements" template="checkout/onepage/agreements.phtml"/>
</block>
...
</checkout_onepage_index>
...
Now we're ready to call and render that block from within the billing step's template. Open that up, get to the place where you want the agreements to appear, and add this line:
<?php echo $this->getChildHtml('agreements') ?>
If you clear your cache and get to the checkout, you should see the agreements appear. That handles rendering, now we have to tie that into validation.
How to Validate Agreements
Because this is normally done at the end of the checkout, we can figure out how it works by examing the checkout's main controller:
app/code/core/Mage/Checkout/controllers/OnepageController.php::saveOrderAction:
public function saveOrderAction()
{
...
if ($requiredAgreements = Mage::helper('checkout')->getRequiredAgreementIds()) {
$postedAgreements = array_keys($this->getRequest()->getPost('agreement', array()));
if ($diff = array_diff($requiredAgreements, $postedAgreements)) {
$result['success'] = false;
$result['error'] = true;
$result['error_messages'] = $this->__('Please agree to all the terms and conditions before placing the order.');
$this->getResponse()->setBody(Mage::helper('core')->jsonEncode($result));
return;
}
}
...
You will essentially copy this condition into the top of the saveBillingAction method, like so:
...
public function saveBillingAction()
{
...
if ($this->getRequest()->isPost()) {
if ($requiredAgreements = Mage::helper('checkout')->getRequiredAgreementIds()) {
$postedAgreements = array_keys($this->getRequest()->getPost('agreement', array()));
if ($diff = array_diff($requiredAgreements, $postedAgreements)) {
$result['success'] = false;
$result['error'] = true;
$result['message'] = $this->__('Please agree to all the terms and conditions before placing the order.');
$this->getResponse()->setBody(Mage::helper('core')->jsonEncode($result));
return;
}
}
...
Notice a key difference here. The $result['error_messages'] was changed to $result['message']. This is done because, unfortunately for the stock checkout, its JavaScript is inconsistent in implementation. So while the order review step will check for error_messages, the billing step looks for messages on the result.
Now that you've displayed your agreements, and wired them up to the controller, you should be able to test this step out. If you don't check the agreements, and continue to the next step, you would get an alert box that says, "Please agree to all the terms and conditions before placing the order."
A long-winded answer, but also very necessary if you have no idea where to begin. Hopefully this helps.
Best Answer
In the various bits of contracting and consulting I've done, the solution is not to solve this problem. The general thinking is
It happens less often than you'd think
When it does happen, it's easier to take both orders and fix things on a business level
Fixing this on a business level means waiting to fulfill the second order until more stock comes in, or if more stock isn't coming you cancel the customer's order and send an apologetic email with an optional coupon or some other low cost fringe benefit so they don't feel bad.