Really, any Nokia smart phone, since at least the Nokia 6600 (or before) have been relatively easy to use for this (and one of the reasons I have taken Nokia phones over others in the past, when tethering was restricted on other devices).

You have been able to do it on any Linux distro, either using straight ppp, or the distro-provided conneciton management, or a desktop-oriented dialer (e.g. kppp).

For various reasons, I use my N900 via kppp most of the time.

Here are relevant portions of my ~/.kde4/share/config/kppprc:

[General]
AutomaticRedial=1
DefaultAccount=3G
DefaultModem=Nokia
DockIntoPanel=1
NumberOfAccounts=1
NumberOfModems=2
PPPDebug=0
RedialOnNoCarrier=1
ShowLogWindow=1

[Account0]
AccountingEnabled=0
Authentication=4
AutoDNS=1
AutoName=0
DefaultRoute=1
ExDNSDisabled=1
Gateway=0.0.0.0
IPAddr=0.0.0.0
Name=3G
Password=\s
Phonenumber=*99#
StorePassword=1
SubnetMask=0.0.0.0
Username=\s
VolumeAccountingEnabled=0
pppdArguments=multipledefaultroutes

[Modem0]
AnswerResponse=CONNECT
AnswerString=ATA
BusyResponse=BUSY
BusyWait=0
ConnectResponse=CONNECT
DLPResponse=DIGITAL LINE DETECTED
Device=/dev/ttyACM0
DialString=ATDT
Enter=CR
EscapeGuardTime=50
EscapeResponse=OK
EscapeString=+++
FlowControl=Hardware [CRTSCTS]
HangUpResponse=OK
HangupString=+++ATH
InitDelay=50
InitResponse=OK
InitString=ATZ
InitString1=AT+CGDCONT=1,"IP","internet"
Name=Nokia
NoCarrierResponse=NO CARRIER
NoDialToneDetection=ATX3
NoDialToneResp=NO DIALTONE
PreInitDelay=50
RingResponse=RING
Speed=57600
Timeout=60
ToneDuration=70
UseLockFile=1
Volume=1
VolumeHigh=M1L3
VolumeMedium=M1L1
VolumeOff=M0L0
WaitForDialTone=1

[Modem1]
AnswerResponse=CONNECT
AnswerString=ATA
BusyResponse=BUSY
BusyWait=0
ConnectResponse=CONNECT
DLPResponse=DIGITAL LINE DETECTED
Device=/dev/rfcomm0
DialString=ATDT
Enter=CR
EscapeGuardTime=50
EscapeResponse=OK
EscapeString=+++
FlowControl=Hardware [CRTSCTS]
HangUpResponse=OK
HangupString=+++ATH
InitDelay=50
InitResponse=OK
InitString=ATZ
InitString1=AT+CGDCONT=1,"IP","internet"
Name=Bluetooth
NoCarrierResponse=NO CARRIER
NoDialToneDetection=ATX3
NoDialToneResp=NO DIALTONE
PreInitDelay=50
RingResponse=RING
Speed=460800
Timeout=60
ToneDuration=70
UseLockFile=1
Volume=1
VolumeHigh=M1L3
VolumeMedium=M1L1
VolumeOff=M0L0
WaitForDialTone=1