Cautiously playing around with supplements I found melatonin to be effective in aiding sleep quality, though not with time to fall asleep. Any suggestions to that effect?

Have you tried taking melatonin sublingually? The rapid absorption leads to a faster onset of sleepiness, which might help (I get extremely sleepy about 10 minutes after sublingual administration). Sublingual melatonin tablets can be found on Amazon.