Rust, \$3^{38\,000\,000}\$ in ~1 minute

How it works

Given position \$n\$, we convert \$3n\$ into a base-\$\frac43\$ representation with digits \$0, 1, 2, 3\$ using a relatively fast divide-and-conquer algorithm. Iterating through these base-\$\frac43\$ digits from most to least significant gives the shifts needed to maintain a three-character sliding window of the Base64 fixed point.

For example, given position \$27\$, we compute

$$3 · 27 = (3210201101)_{\frac43},$$

so we can jump the sliding window to the following positions (in units of \$\frac13\$ of a 6-bit character).

$$0 · \frac43 + 3 = 3, \quad 3 · \frac43 + 2 = 6, \quad 6 · \frac43 + 1 = 9, \quad 9 · \frac43 + 0 = 12, \\ 12 · \frac43 + 2 = 18, \quad 18 · \frac43 + 0 = 24, \quad 24 · \frac43 + 1 = 33, \quad 33 · \frac43 + 1 = 45, \\ 45 · \frac43 + 0 = 60, \quad 60 · \frac43 + 1 = 81.$$

Usage

Accepts a base-ten integer on STDIN, and outputs a character to STDOUT.

$ cargo build --release
$ python3 -c 'import gmpy2; print(gmpy2.mpz(3) ** 38000000)' > /tmp/in
$ time target/release/base64 < /tmp/in
1

real    1m0.092s
user    1m0.023s
sys     0m0.068s

Code

Cargo.toml

[package]
name = "base64"
version = "0.1.0"
edition = "2021"

[dependencies]
rug = "1.19.0"

src/main.rs

use rug::Integer;
use std::io::BufRead;

const ALPHABET: &[u8] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

fn encode_low(n: Integer, k: u32) -> (Integer, Integer, Integer) {
    if k == 1 {
        let t = n * 3;
        let l = Integer::from(&t & 3);
        (3.into(), t >> 2, l)
    } else {
        let k0 = k / 2;
        let (p0, h0, l0) = encode_low(&n & !((!Integer::ZERO) << (k0 * 2)), k0);
        let k1 = k - k0;
        let (p1, h1, l1) = encode_low((n >> (k0 * 2)) * &p0 + h0, k1);
        (p1 * p0, h1, l1 << (k0 * 2) | l0)
    }
}

fn encode(n: Integer) -> Integer {
    if n == 0 {
        Integer::ZERO
    } else {
        let k = (n.significant_bits() + 1) / 2;
        let (_, h, l) = encode_low(n, k);
        encode(h) << (k * 2) | l
    }
}

fn char_at(n: Integer) -> char {
    let e = encode(n);
    let mut a: u32 = 0x566d30;
    for i in (0..e.significant_bits()).step_by(2).rev() {
        let k = 6 - e.get_bit(i + 1) as u32 * 4 - e.get_bit(i) as u32 * 2;
        a = (ALPHABET[((a >> (k + 12)) & 0x3f) as usize] as u32) << 16
            | (ALPHABET[((a >> (k + 6)) & 0x3f) as usize] as u32) << 8
            | (ALPHABET[((a >> k) & 0x3f) as usize] as u32);
    }
    char::from((a >> 16) as u8)
}

fn main() {
    for line in std::io::stdin().lock().lines() {
        let n: Integer = line.unwrap().parse().unwrap();
        println!("{}", char_at(n));
    }
}

JavaScript (Node.js), 218 bytes

var btoa = s => Buffer.from(s).toString('base64');
var fp = (n, m = n + 1n) => m > 9n ? btoa(fp(n / 4n * 3n, (m + 3n) / 4n * 3n)).slice(Number(n % 4n), Number(n % 4n + m - n)) : "Vm0wd2QyU".slice(Number(n), Number(m));

Try it online! Link includes test cases. Using Node because it has a reasonably convenient btoa builtin, so it won't win any speed records but at least it scores reasonably well in time complexity.

Since the above code is recursive and stack space is expensive, here's an iterative version, although this only returns one character at a time so there's only one test case: Try it online!

var btoa = s => Buffer.from(s).toString('base64');
function fp(n) {
	stack = [];
	while (n) {
		stack.push(Number(n % 4n));
		n = n / 4n * 3n;
	}
	s = "Vm0wd2QyU";
	while (stack.length) s = btoa(s).substr(stack.pop(), 9);
	return s[0];
}
console.log(fp(3n ** 100000n));