Python 2, 150 149 127 144 bytes

lambda n:min((len(c(n,b))+len(set(c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n/b,b,chr(n%b+48+7*(n%b>9))+s)or s or'0'

Try it online!

Python 3, 136 bytes

lambda n:min((len((*c(n,b),**c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!

Python 3.8 (pre-release), 131 bytes

lambda n:min((len((*(x:=c(n,b)),**x)),b,x)for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!

c converts a base 10 number to any base (2-36), and the first (anonymous) function finds the smallest result.

05AB1E, 16 14 bytes

-1 byte thanks to Kevin Cruijssen

₆LBāøΣнDÙìg}1è

Try it online!

Or add R)» at the end to conform exactly to the specified output format, but most other answers didn't bother.

Explanation:

₆L # range 1..36
 B # convert the input to each of those bases
 āø # enumerate (pair each element with its 1-based index)
Σ } # sort by
 g # length
 н # of the first element
 ì # concatenated to
 DÙ # itself, uniquified
1è # take the second entry (first will always be base 1)

Japt v2.0a0 -gS, 24 23 bytes

Not pretty, but it does the job. +2 bytes for the completely unnecessary requirement that output be uppercase.

37o2@sX u ¸iXÃñÈÌiXÌâ)l

Try it

37o2@sX u ¸iXÃñÈÌiXÌâ)l :Implicit input of integer
37o2 :Range [2,37)
 @ :Map
 sX : Convert the input to a base-X string
 u : Uppercase
 ¸ : Split on spaces (there are none, so this returns a singleton array)
 iX : Prepend X
 Ã :End map
 ñ :Sort by
 È :Pass each X through the following function
 Ì : Last element of X
 i : Prepend
 XÌâ : Last element of X, deduplicated
 ) : End prepend
 l : Length
 :Implicit output of the first sub-array, joined with spaces

JavaScript (ES6),  87 85  101 bytes

Edit: +16 useless bytes to comply with the strict output format

n=>(g=m=>--b>2?g(m<(v=new Set(s=n.toString(b)).size+s.length)?m:(o=b+' '+s.toUpperCase(),v)):o)(b=37)

Try it online!

Charcoal, 38 bytes

Ｎθ≔ＥＥ³⁴↨θ⁺²ιＬ⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηＩη ↥⍘θη

Try it online! Link is to verbose version of code. Explanation:

Ｎθ

Input the integer.

≔ＥＥ³⁴↨θ⁺²ι

Convert it from base 2 to base 36...

Ｌ⁺ιΦι⁼λ⌕ικη

... deduplicate, concatenate, and take the length.

≔⁺²⌕η⌊ηη

Take the index of the minimum complexity and add 2 to get the base.

Ｉη ↥⍘θη

Print the base and the integer converted to that base in upper case.

Stax, 19 bytes

Ç╛;ⁿY3█↕(╖S♪*ò▌?½╦l

Run and debug it

No fancy algorithm, just straightforward brute force. About a third of the program is format-wrangling for the precise output rules.

Bonus program: Output for [1..1000]

Jelly, 25 bytes

bⱮ36µQL+LN)Mḟ1Ḣ,ị‘ịØBʋ¥⁸K

Try it online!

A monadic link taking an integer as its argument and returning a Jelly string of the desired format. If a two-item list was acceptable output (as per most challenges), could save 2 bytes. If base 1 were acceptable for the edge case of 1 as input, could save a further 2 bytes.

Japt v2.0a0, 32 bytes

T=2o37 ñ@sX Ê+UsX â ÊÃÎT+S+UsT u

Can save two bytes if I can reverse the order, and can save 2 more if uppercase wasn't required.

Try it

Perl 5, 161 bytes

sub f$X=99;for$b(2..36)$_=c($_[0],$b);$x=uniq(/./g)+y///c;($X,$B,$C)=($x,$b,$_)if$x<$X$B,$C
sub cmy($n,$b)=@_;$n?c(int$n/$b,$b).chr(48+$n%$b+7*($n%$b>9)):''

Try it online!

Wolfram Language (Mathematica), 109 bytes

Print[a=OrderingBy[#~IntegerDigits~Range@36,Tr[1^#]+Tr[1^Union@#]&][[1]]," ",ToUpperCase[#~IntegerString~a]]&

OrderingBy was introduced in Mathematica 12.0, which TIO does not seem to have updated to yet.

PHP, 124 119 bytes

for($i=36;$b=strtoupper(base_convert($argn,10,--$i));$o[strlen($b.count_chars($b,3))]="$i $b");krsort($o);echo end($o);

Try it online!

A shame about the +12 bytes in PHP to uppercase the output... but... anyway.

Perl 6, 55 bytes

~map($^b,.base($b),2..36).min:.[*]+.Seto*[1].comb

Try it online!

Python 2, 140 135 bytes

lambda n:min([(b,g(n,b))for b in range(2,36)],key=lambda(b,s):len(s)+len(set(s)))
g=lambda n,b:n and g(n/b,b)+chr(n%b+48+7*(n%b>9))or''

Try it online!

Brachylog, 44 bytes

∧Y≜∧36≥Xℕ₂≜&ḃ↙X Zd,Zl≡Y∧XwṢwZ-₁₀;Ạụᵗ∋₍ᵐwᵐ

Try it online!

This hurt a bit to write.