We solve the Hamiltonian and momentum constraints of General Relativity for two black-holes with nearly extremal spins or ultra-relativistic boosts in the puncture formalism. We use a non-conformally-flat ansatz with an attenuated superposition of two conformally Kerr or Lorentz-boosted-Schwarzschild 3-metrics and their corresponding extrinsic curvatures. We compare evolutions of these data with the standard Bowen-York conformally-flat ansatz (technically limited to intrinsic spins S/M2ADM=0.928 and boosts P/MADM=0.897), finding an order of magnitude smaller burst of spurious radiation. As a case study, we evolve two equal-mass black-holes from rest with an initial separation of d=12M and spins Si/m2i=0.99, compute the waveforms produced by the collision, the energy radiated, and the recoil of the final remnant black-hole. We find that the black-hole trajectories curve at closer separation, which leads to the radiation of angular momentum. We also study orbiting (nonspinning) black-hole binaries and binaries with the two black-holes boosted towards each other at relativistic speeds. These non-spinning data also show a substantial reduction in the non-physical initial burst of radiation which leads to cleaner waveforms. Finally, we study different choices of the initial lapse and lapse evolution equation in the moving punctures approach to improve the accuracy and efficiency of the simulations.