Hi
In regards your questions:
- Would simple spanning tree work in this scenario?
Yes. (unfortunately the 4100 doesn;t support MSTP but you can use the RSTP).
- Would I need a trunk link between the cores?
You should plan for the RSTP very well, so one 4100 playing as a Root, and the other as a Backup, and say 2Gig uplinks between them for better performance if you have some servers or ... connected to both cores.
-Is there a better (more elegant!) way of achieving Core redundancy?
Yes
by replacing the 4100 with 5400, so you can have L3 redudancy as well as better L2 redudancy.
Explanation:
Now with this scenario you can have L2 redudancy based on the old RSTP protocol.
With the 5400, you can improve this L2 redudancy with MSTP which will load balance between Vlans, so you don;t have a blocked port (and you've paid for the cable already but with RSTP its just blocked and doing nothing).
Also
You can get L3 redudancy - VRRP and that need a license.
If your budget can;t afford 2 of 5400, you can have 2 of the 5300 which support L3 redundancy - XRRP and also MSTP.
Good Luck !!!