Afaik 'nästa' only means 'next' in the sense of "the following", whereas 'next to' is more like a preposition and thus translated into 'bredvid'.

Well, you would probably say "Vem sitter bredvid mig och ljuger?" or something like that. "Vem ligger bredvid mig och ljuger?" maybe :).

vid mig - by me

bredvid mig - next to me

nästa is 'next' in a temporal sense, like nästa vecka 'next week', so it doesn't work here.
intill and bredvid are both 'next to' or 'beside' but intill is a little closer, often implying contact. Both of these work here.