Ethernet Auto Negotiation Timeout
I seem to be facing an issue where the auto-negotiation is timing out.

Auto-negotiation is typically handled directly by the PHY.  In every chip I have encountered, it should happen automatically without any setup as long as...

The chip has power
You aren't holding the chip in reset.
The +/- in each differential pair is not swapped
The TX and RX pairs are not swapped.  Remember, when connecting directly to a device without going through a hub you need a crossover cable (or a PHY with auto MDIX enabled).
You didn't disable auto-negotiation in the MII management registers by writing incorrect values in software.

You can tell that auto-negotiation completed by looking at the network connection properties in windows.  If it shows a connection speed (anything at all) then it worked.

Prior to this I have attempted to assign an IP-Address to the device
and then ping that IP address (but no response was received).

SUBNET
The echo request and echo reply (AKA ping) is part of the ICMP protocol.  ICMP runs on top of UDP and IPV4 or IPV6.  By default windows won't communicate to a device that is in a different sub-net.
In windows you must have (SRC_IP_ADDR &amp; MASK) == (DST_IP_ADDR &amp; MASK) for the source to be able to send the message. For example if your mask is FF.FF.00.00 then the upper two bytes of the PC IP address must match the upper two bytes of the device IP address
So make sure the sub-net mask and IP address in windows matches the IP address for your device.  Otherwise you won't be able to communicate via IPV4/IPV4, UDP, or TCP (so no pings).
ARP TABLE
When windows sends a non-broadcast IP packet over Ethernet, it needs to know what to put into the MAC layer destination address field.  This information is contained in an ARP table.  The first time windows trys to send a packet to a new IP address it won't know the destination MAC address, so instead it sends an ARP request (using a broadcast MAC address) to find out.  The destination replies with another ARP packet and then windows updates its table.  At that point windows can actually send the packet.  You have a few options here.

Your device implements the ARP protocol (which is standard in most network stacks).
You manually make an ARP table entry in windows.
You only send packets using the broadcast IP address (FF.FF.FF.FF), in which case windows won't need ARP since it will use the broadcast MAC address (FF.FF.FF.FF.FF.FF) to send the packet.

Option 3 is a really good option for debug because it eliminates both ARP and the sub-net mask as possible failure points.  But be aware that broadcast IP packets typically won't propagate through the upstream port of any Ethernet switches or routers. (but it will pass between any other ports on the switch).
PC SIDE IP ADDRESS:
If you are running windows on the laptop you need to be aware that (by default) windows is going to expect that there is a DHCP server accessible from each Ethernet port.  When you plug in your device windows is going to try and obtain an IP address over DHCP.  It can take a long time before windows gives up.  After DHCP fails it will then try to use APIPA to obtain an address (basically by choosing a desired address and then using ARP to verify that no-one else is using it).  In any case, during that whole process you can't send any IP packets (at least from normal code thats not part of an NDIS driver).
From personal experience, all three of these options work.

Configure your Ethernet port to use a static IP address.
Plug in an Ethernet switch between your device and the laptop.  Many switches implement a DHCP server and will give windows an address.
Implement a DHCP server in your device, and let it give windows an address.

Also note that if you plug in an Ethernet port connected to a PC running Windows, then Windows will send out all kinds of packets trying to figure out what its attached to and to see if it can get to the Internet.  So be prepared to receive all kinds of unexpected packets during debug.