EDIT: Apparently things changed in 10.9 significantly for making the boot disk - Not sure why the createinstallmedia didnt work, but apparently what I screwed up was not first installing the base onto the drive to make it bootable.
Actually, I did repartition both the flash disk and the hard drive, making sure it was set to GUID. And that wouldn't explain why the DVD didn't work - there's no partition table, thats just a straight burn.