Smallest element distance between two lists
DistanceMatrix is fast. It evaluates multiple times in the SameTest. If you rewrite your code, you can see the difference:
min=Min[DistanceMatrix[testlist1,testlist2]];//AbsoluteTiming
{0.000501174,Null}
Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=min&)]//AbsoluteTiming
{0.0236643,{0.5}}
VS original code
Intersection[testlist1,testlist2,SameTest->(Abs[#1-#2]<=Min[DistanceMatrix[testlist1,testlist2]]&)]//AbsoluteTiming
{5.39343,{0.5}}
DistanceMatrix will stay in the future versions of Mathematica. Also you can find DistanceMatrix in HierarchicalClustering package or use this code.
Answering on your 3rd question, you can make it so:
mat=DistanceMatrix[testlist1,testlist2];
pos=Position[mat,Min@mat]
{{3,2}}
testlist1[[pos[[;;,1]]]]
{0.5}
testlist2[[pos[[;;,2]]]]
{0.4957}
mind[l1_List, l2_List] :=
MinimalBy[Table[{k, First@Nearest[l1, k]}, {k, l2}], Norm]
RepeatedTiming[mind[testlist1, testlist2]]
(* {0.0061, {{0.0057, 0.}}} *)
For huge lists you may change Table
for ParallelTable